-
若干图的广义字典积的点可区别边染色
- 田双亮
-
2014, 49(06):
31-34.
doi:10.6040/j.issn.1671-9352.0.2013.649
-
摘要
(
1189 )
PDF (613KB)
(
636
)
收藏
-
相关文章 |
多维度评价
在图G与不相交图序列hn=(Hi)i∈{0,1,…,n-1}的广义字典积 G[hn]中, 若Hi-H, i=0,1,…,n-1, 则将G[hn]记为G[H], 其中G[H]是G与H的字典积。 图G的点可区别边染色所需最少的颜色数称为G的点可区别边色数, 记为χ′vd (G)。 对任一满足χ′vd (G)=Δ(G)的图G, 给出了参数χ′vd (G[hn])的两个上界, 并证明这些上界是可达到的, 其中 hn=(Hi)i∈{0,1,…,n-1}中的每一个Hi均为m阶简单图。 另外证明了: 如果χ′vd(G)=Δ(G), χ′vd(H)=Δ(H)且Δ(G[H])=Δ(H[G]), 则 χ′vd(G[H])=χ′vd(H[G]), 其中G与H分别为n阶与m阶的简单图。