若干图的倍图的邻点可区别边_全_染色_何雪

（ 1）
对任意 n≥3 阶的简单图 G ， 有 χ' as （ D （ G ） ） ≤ χ ' as （ G ） + Δ （ G ） 。 为证明结论成立， 仅需给出图 D （ G ） 的一个（ χ ' 邻点可区别边染色。 根据式 （ 1 ） ， as （ G ） + Δ （ G ） ） -
可分两步构造 D （ G ） 的邻点可区别边染色 σ： 先用 χ ' as （ G ） 种颜色对 G 及其拷贝 G ' 分别进行邻点可区别边染 色， 使得 G ' 与 G 中对应边染相同的颜色， 所用颜色的集合记为 A 。然后， 用 Δ（ G ） 种新的颜色对 H 进行正常 边染色， 所用颜色的集合记为 B 。 v ∈V （ G ） 或 u ， v ∈V （ G ' ） ， C σ （ u） ∩A ≠ 对 D （ G ） 中任意相邻的两个顶点 u 与 v ， 若 u， 则由 σ 定义可知， C σ （ v ） ∩A 。又因 A ∩B = 及 C σ （ u） = （ C σ （ u） ∩A ） ∪（ C σ （ u） ∩B ） ， 所以 C σ （ u） ≠ C σ （ v ） 。 若 u 与 v 分别 在 V （ G ） 与 V （ G ' ） 中， 不妨设 u∈V （ G ） ，v ∈V （ G ' ） 。因 C σ （ u） ∩ A = C σ （ u' ） ∩ A 及 C σ （ u' ） ∩ A ≠ C σ （ v ） ∩ A， u 与 v 是可区别的， 其中 u' 是 G ' 中 u 的拷贝点， 所以 C σ （ u） ≠C σ （ v ） 。因此， 在染色 σ 下， 即 σ 是 D（ G ） 的一个（ χ ' 邻点可区别边染色。故定理成立。 as （ G ） + Δ （ G ） ） ［ 1］ ） ，n≥1 ， 对 3 n 阶的圈 C 3n ， 因为 χ ' 由引理 1 与定理 1 可得，χ ' as （ C 3 n ） = 3 （ 见文献 as （ D （ C 3 n ） ） = 5 。 对
［3 ］ 定义 3
x2 ， …， x n ｝ 的图 G 的倍图 D （ G ） 是指具有顶点集与边集 具有顶点集｛ x1 ， V （ D （ G ） ） = ｛ x1 ， x2 ， …， x n ｝ ∪｛ x' x' …， x' 1， 2， n｝ ，
E （ D （ G ） ） = E （ G ） ∪｛ x' i， j = 1， 2， …， n｝ ∪｛ x i x' i x' j | x i x j ∈E （ G ） ， i， j = 1， 2， …， n｝ j | x i x j ∈E （ G ） ， 的图。 ｛ x' x' …， x' 由定义 3 可知， 将其记为 G ' ， 且称它为 G 的拷贝。 1， 2， n ｝ 在 D （ G ） 中的导出子图与 G 同构 ， 12， 4］ 关于结构较简单的图， 如路、 圈、 完全图、 二部图、 树、 轮、 扇等， 文献［ 得到了它们的邻点可区别边 色数或全色数。由于图的结构运算是构造图的重要方法和手段 ， 因此， 研究运算图的邻点可区别边染色与全 染色有助于确定一般图类的相应染色数 。常见的图运算有图的笛卡尔积、 图的联、 图的字典积以及图的倍图 59］ 研究了一些特殊图的笛卡尔积的邻点可区别边染色或全染色 ， 如路和完全图的笛卡尔积、 网 等。文献［ k格图（ 路与路的笛卡尔积） 、 立方体（ k 个 2 阶路的笛卡尔积 ） 、 二部图与完全图的笛卡尔积、 二部图与圈的 10 11］ 研究了扇的倍图的邻点可区别边染色和完全图的倍图的邻点可区别全染色 。本文 笛卡尔积等； 文献［ 主要研究一些特殊图的倍图的邻点可区别边染色与全染色 ， 给出了相应染色数的上界， 并确定了完全图与树 12 ］ 。 等特殊图的倍图的邻点可区别边色数和全色数 。文中未加说明的术语及记号参见文献［ 为了研究倍图的邻点可区别边染色与全染色 ， 我们首先给出以下引理。 n对任意整数 n≥3 ， 正则完全二部图 K n， 边染色， 使得在 K n， n 存在一个 nn 的一个完美匹配 不同的边染不同的颜色。 中，
0
引言
本文所考虑的图 G 都是有限无向的简单连通图， 用 V （ G ） 与 E （ G ） 分别表示 G 的顶点集和边集， 并用 Δ（ G ） 表示 G 的最大度。
［1 ］ 定义 1
对阶至少为 3 的简单图 G ， 如果 G 的一正常 k边染色 σ 满足对任意 uv ∈E （ G ） ， 有 C σ （ u） ≠
64
山
东
大
学
学
报
（理
学
版）
第 50 卷
Cσ（ v） ， 其中 C σ （ u） = ｛ σ（ uv ） | uv ∈E （ G ） ｝ ， 则称 σ 为 G 的一 k邻点可区别边染色， 或称为邻强边染色， 最 小的 k 值称为 G 的邻点可区别边色数， 记为 χ ' as （ G ） 。 定义 1 中的 C σ （ u） 称为点 u 在 σ 下的色集合。由定义 1 ， 显然有以下引理。 引理 1 定义 2 对阶至少为 3 的简单图 G ， 若存在两个相邻的最大度点， 则 χ' as （ G ） ≥ Δ （ G ） + 1 。 对阶至少为 2 的简单图 G ， 如果 G 的一正常 k全染色 σ 满足对任意 uv ∈E （ G ） ， 有 S σ （ u） ≠
第 50 卷 Vol． 50
第4 期 No． 4
山
东
大
学
学
报
（理
学
版）
Journal of Shandong University （ Natural Science）
19352. 0. 2014. 327
2015 年 4 月 Apr． 2015
［13 ］ 引理 3
1
主要结论及其证明
x2 ， …， xn ｝ ， x2 ， …， x n ｝ ∪｛ x' x' …， x' 设 G 的顶点集为｛ x1 ， 其倍图 D （ G ） 的顶点集为｛ x1 ， 1， 2， n ｝ 。 根据倍图的
H 与 G '， 定义， 可将 D （ G ） 分解为三个边不交的子图 G ， 即有 D （ G ） = G ∪H ∪G ' ， H 是具有二分类（ V （ G ） ， V （ G ' ） ） 且最大度为 Δ（ G ） 的二部图。 其中 G ' 为 G 的拷贝， 关于 G 的倍图 D （ G ） 的邻点可区别边色数的上界， 我们有以下结论： 定理 1 证明
9352 （ 2015 ） 04006304 文章编号： 1671-
若干图的倍图的邻点可区别边 （ 全 ） 染色
何雪， 田双亮
*
（ 西北民族大学数学与计算机科学学院 ，甘肃 兰州 730030 ）
摘要： 设 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 ） 的以上两个参数的上界 ， 树， 确定了它们的倍图的邻点可区别边色数与全色数的精确值 。 关键词： 倍图； 邻点可区别边染色； 邻点可区别全染色 中图分类号： O157. 5 文献标志码： A
0715 ； 网络出版时间： 20150305 10∶ 15 收稿日期： 2014网络出版地址： http： / / w w w ． cnki． net / kcms / detail /37． 1389． N． 20150305． 1015． 001． html 基金项目： 西北民族大学研究生科研创新项目 （ ycx14146 ） ； 西北民族大学科研创新团队计划资助 mail： hexuebeautiful@ 163． com 作者简介： 何雪（ 1988 － ） ，女，硕士，研究方向为图论与组合优化． E* 通讯作者： 田双亮（ 1965 － ） ，男，硕士，教授，研究方向为图论及组合优化． Email： sl_tian@ 163． com
［2 ］
Sσ （ v ） ， 其中 S σ （ u） = ｛ σ（ u） ｝ ∪｛ σ（ uv ） | uv ∈E （ G ） ｝ ， 则称 σ 为 G 的一 k邻点可区别全染色， 最小的 k 值称 记为 χ at （ G ） 。 为 G 的邻点可区别全色数， 定义 2 中的 S σ （ u） 称为点 u 在 σ 下的色集合。由定义 2 ， 显然有以下引理。 引理 2 对阶至少为 2 的简单图 G ， 若有两个相邻的最大度点， 则 χ at （ G ） ≥Δ（ G ） + 2 。
Adjacent vertex-distinguishing edge / total colorings of double graph of some graphs
HE Xue，TIAN Shuangliang *
（ School of M athematics and Computer Science，Northw est University for Nationalities，Lanzhou 730030 ，Gansu，China） Abstract： Let G be a simple graph w ith vertex set V （ G ） and edge set E （ G ） ． An edgecoloring σ of G is called an adjacent vertex distinguishing edgecoloring of G if C σ （ u） ≠C σ （ v ） for any uv ∈E（ G ） ，w here C σ （ u） denotes the set of colors of edges incident w ith u． A totalcoloring σ of G is called an adjacent vertex distinguishing totalcoloring of G if S σ （ u） ≠S σ （ v ） for any uv ∈E（ G ） ，w here S σ （ u） denotes the set of colors of edges incident w ith u together w ith the color assigned to u． The minimum number of colors required for an adjacent vertexdistinguishing edgecoloring （ resp． totalcoloring ） of G is called adjacent vertexdistinguishing 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 determined． Key words： double graph； adjacent vertexdistinguishing edge coloring ； adjacent vertexdistinguishing total coloring