山东大学学报（理学版）
山東大學學報（理學版）
산동대학학보（이학판）
JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
2015年
4期
63-66
,共4页
倍图%邻点可区别边染色%邻点可区别全染色
倍圖%鄰點可區彆邊染色%鄰點可區彆全染色
배도%린점가구별변염색%린점가구별전염색
double graph%adjacent vertex-distinguishing edge coloring%adjacent vertex-distinguishing total coloring
设 G 是具有顶点集 V（G）和边集 E（G）的简单图。如果 G 的一正常边染色σ满足对任意 uv∈E（G），有Cσ（u）≠Cσ（v），其中 Cσ（u）为点 u 的关联边所染颜色构成的集合，则称σ为 G 的邻点可区别边染色。如果 G 的一正常全染色σ满足对任意 uv∈E（G），有 Sσ（u）≠Sσ（v），其中 Sσ（u）表示点 u 及 u 的关联边所染颜色构成的集合，则称σ为 G 的邻点可区别全染色。图 G 的邻点可区别边（或全）染色所需的最少的颜色数，称为 G 的邻点可区别边（或全）色数，并记为χ′as （G）（或χat （G））。给出了图 G 的倍图 D（G）的以上两个参数的上界，并对完全图与树，确定了它们的倍图的邻点可区别边色数与全色数的精确值。
設 G 是具有頂點集 V（G）和邊集 E（G）的簡單圖。如果 G 的一正常邊染色σ滿足對任意 uv∈E（G），有Cσ（u）≠Cσ（v），其中 Cσ（u）為點 u 的關聯邊所染顏色構成的集閤，則稱σ為 G 的鄰點可區彆邊染色。如果 G 的一正常全染色σ滿足對任意 uv∈E（G），有 Sσ（u）≠Sσ（v），其中 Sσ（u）錶示點 u 及 u 的關聯邊所染顏色構成的集閤，則稱σ為 G 的鄰點可區彆全染色。圖 G 的鄰點可區彆邊（或全）染色所需的最少的顏色數，稱為 G 的鄰點可區彆邊（或全）色數，併記為χ′as （G）（或χat （G））。給齣瞭圖 G 的倍圖 D（G）的以上兩箇參數的上界，併對完全圖與樹，確定瞭它們的倍圖的鄰點可區彆邊色數與全色數的精確值。
설 G 시구유정점집 V（G）화변집 E（G）적간단도。여과 G 적일정상변염색σ만족대임의 uv∈E（G），유Cσ（u）≠Cσ（v），기중 Cσ（u）위점 u 적관련변소염안색구성적집합，칙칭σ위 G 적린점가구별변염색。여과 G 적일정상전염색σ만족대임의 uv∈E（G），유 Sσ（u）≠Sσ（v），기중 Sσ（u）표시점 u 급 u 적관련변소염안색구성적집합，칙칭σ위 G 적린점가구별전염색。도 G 적린점가구별변（혹전）염색소수적최소적안색수，칭위 G 적린점가구별변（혹전）색수，병기위χ′as （G）（혹χat （G））。급출료도 G 적배도 D（G）적이상량개삼수적상계，병대완전도여수，학정료타문적배도적린점가구별변색수여전색수적정학치。
Let G be a simple graph with vertex set V(G)and edge set E(G).An edge-coloring σof G is called an adjacent vertex distinguishing edge-coloring of G if Cσ(u)≠Cσ(v)for any uv∈E(G),where Cσ(u)denotes the set of colors of edges incident with u.A total-coloring σof G is called an adjacent vertex distinguishing total-coloring of G if Sσ(u)≠Sσ(v)for any uv∈E(G),where Sσ(u)denotes the set of colors of edges incident with u together with the color assigned to u.The minimum number of colors required for an adjacent vertex-distinguishing edge-coloring (resp. total-coloring)of G is called adjacent vertex-distinguishing edge (resp.total)chromatic number,and denoted byχ′as (G)(resp.χat (G)).The upper bounds for these parameters of the double graph D(G)of graph G are given in this paper.Specifically,the exact value of these parameters for the double graph of complete graphs and trees are deter-mined.
