两类正则图的邻点全和可区别全染色

常景智; 杨超; 程银万; 王芹; 姚兵

doi:10.13718/j.cnki.xdzk.2022.04.014

摘要: 设f：V(G)∪E(G) [1，k]是图G的一个非正常k-全染色. 令φ(x)=f(x)+$ \sum\limits_{e \ni x} {f\left( e \right)} + \sum\limits_{y \in N\left( x \right)} {f\left( y \right)} $，其中N(x)={y∈V(G)|xy∈E(G)}. 对任意的边uv∈E(G)，如果有φ(u)≠φ(v)成立，则称f是图G的一个邻点全和可区别(简记NFSD)k-全染色. 图G的邻点全和可区别全染色中最小的k值称为G的邻点全和可区别全色数，记为fgndi_Σ(G). 通过构造染色函数法，确定了广义Petersen图和循环图的邻点全和可区别全色数.

Abstract: Let f: V(G)∪E(G) [1, k] be a non-proper total k-coloring of G. Define a weight function about total coloring as φ(x)=f(x)+$ \sum\limits_{e \ni x} {f\left( e \right)} + \sum\limits_{y \in N\left( x \right)} {f\left( y \right)} $, where N(x)={y∈V(G)|xy∈E(G)}. If φ(u)≠φ(v) for any edge uv∈E(G), then f is called a neighbor full sum distinguishing total k-coloring of G. The smallest value k in neighbor full sum distinguishing total coloring of graph G is called the neighbor full sum distinguishing total chromatic number of G and denoted by fgndi_Σ(G). The neighbor full sum distinguishing total chromatic number of generalized Petersen graphs and Circular graphs are determined by constructing coloring function method.

Key words:

non-proper total coloring /
neighbor full sum distinguishing total coloring /
neighbor full sum distinguishing total chromatic number /
regular graphs .

全文HTML

开放科学(资源服务)标识码(OSID):
图的可区别染色问题是图论中的经典问题之一，随着可区别染色问题被广泛应用于计算机科学、生物学以及网络安全等领域，这一问题被越来越多的国内外学者所研究. 近年来，关于把点和边所染颜色相加的可区别染色问题引起了人们的极大关注. 文献[1]介绍和研究了图的邻和可区别边染色，并提出下述著名的1-2-3猜想：

猜想1^[1](1-2-3猜想)  设G为一个阶数至少为3的简单连通图，则gndi_Σ(G)≤3.

文献[2]证明了阶数至少为3的简单连通图的邻和可区别边色数不超过5. 关于邻和可区别边染色的相关研究见文献[3-6]. 文献[7]提出了图的邻和可区别全染色的概念，并给出了此定义下的1-2猜想：

猜想2^[7](1-2猜想)  设G为一个简单连通图，则tgndi_Σ(G)≤2.

文献[8]得到了任意图的邻和可区别全色数不超过3. 文献[9]考虑把任意点的关联边与其邻点所染颜色相加，定义了图的邻点被扩展和可区别全染色，且得到了一些特殊图的邻点被拓展和可区别全色数. 文献[10]研究了仙人掌图的邻点被拓展和可区别全染色. 不仅如此，文献[9]又在邻点被扩展和可区别全染色的基础上考虑加上点本身的颜色，介绍了下述关于图的一类新染色——邻点全和可区别全染色：

定义1^[9]  设f：V(G)∪E(G) [1，k]是图G的一个非正常k-全染色. 令

其中

对任意的边uv∈E(G)，如果有φ(u)≠φ(v)成立，则称f是图G的一个邻点全和可区别(简记NFSD)k-全染色. 图G的邻点全和可区别全染色中最小的k值称为G的邻点全和可区别全色数，记为fgndi_Σ(G).

本文研究了广义Petersen图和循环图的邻点全和可区别全染色问题，确定了它们的邻点全和可区别全色数. 文中涉及的染色均为非正常的，不失一般性，约定下文证明过程中凡是未被染色的点和边均染颜色1.

1. 广义Petersen图

定义2  广义Petersen图P(n，k)(n≥3，1≤k＜$ \frac{2}{n}$)是由顶点集V={a_i，b_i|i∈[0，n-1]}和边集E={a_ia_i+1，a_ib_i，b_ib_i+k|i∈[0，n-1]}构成的一类三正则图.

P(n，k)具有以下性质：(a) g=gcd(n，k)；(b) $ p = \frac{g}{n}$. 其中g表示外圈C=a₀a₁…a_n-1a₀内部所包含的不交圈的个数，且每个不交圈的长度均为p，外圈C内部所有的不交圈统称为内圈.

定理1  当n为偶数，k为奇数时，fgndi_Σ(P(n，k))=2；其他情形时，fgndi_Σ(P(n，k))≤3.

由定义2知P(n，k)是一类三正则图，则fgndi_Σ(P(n，k))≥2. 定理1分以下3个引理证明：

引理1  当n为偶数，k为奇数时，fgndi_Σ(P(n，k))=2.

证  定义P(n，k)的一个2-全染色f：f(a_ia_i+1)=f(a_ib_i)=f(a_ib_i+k)=1，f(a_i)=2(i为奇数)，f(b_i)=2(i为偶数). 由染色f可得P(n，k)中各点的权重为：φ(a_i)=10(i为奇数)，φ(a_i)=8(i为偶数)，φ(b_i)=8(i为奇数)，φ(b_i)=10(i为偶数). 因b_i总与b_i+k相连，所以内圈中的相邻点下标的奇偶性不同，则有φ(b_i)=10(i为偶数)≠φ(b_i)=8(i为奇数)，证毕.

引理2  当n为偶数，k为偶数时，fgndi_Σ(P(n，k))≤3.

证  根据不交圈的长度p，分以下3种情形讨论：

情形1  当p≡0(mod 3)时，令e_i^m=b_ib_i+k，i∈[0，p-1]，m∈[1，g]. 设f₁为P(n，k)的一个3-全染色，f₁定义如下：f₁(e_i^m)=1(i≡0(mod 3))，f₁(e_i^m)=2(i≡1(mod 3))，f₁(e_i^m)=3(i≡2(mod 3))，f₁(a_ib_i)=2(i为奇数). 可得外圈点的权重φ(a_i)=7(i为偶数)，φ(a_i)=8(i为奇数). 便于叙述，把内圈点b_i按内圈个数g依次重新标号为v_I^m，I∈[1，p]，m∈[1，g]. 例如P(20，4)包含4个不交圈，每个圈长度为5，那么原来的点b₀，b₄，b₈，b₁₂，b₁₆转变为点v₁¹，v₂¹，v₃¹，v₄¹，v₅¹，点b₁，b₅，b₉，b₁₃，b₁₇转变为点v₁²，v₂²，v₃²，v₄²，v₅²等，依次类推. 当m为奇数时，φ(v_I^m)=8(I≡2(mod 3))，φ(v_I^m)=9(I≡1(mod 3))，φ(v_I^m)=10(I≡0(mod 3))；当m为偶数时，φ(v_I^m)=9(I≡2(mod 3))，φ(v_I^m)=10(I≡1(mod 3))，φ(v_I^m)=11(I≡0(mod 3)).

情形2  当p≡2(mod 3)时，设f₂为P(n，k)的一个3-全染色，f₂定义如下：f₂(e_i^m)=1(i≡0(mod 3))，f₂(e_i^m)=2(i≡1(mod 3))，f₂(e_i^m)=3(i≡2(mod 3))，f₂(a_ib_i)=2(i为奇数)，f₂(a_i)=3，i∈[0，g-1]. 先不考虑染色为3的外圈点及其在外圈中的相邻点，则有φ(a_i)=7(i为偶数)，φ(a_i)=8(i为奇数)，φ(a_n-1)=10，φ(a_g)=9. 对于颜色为3的外圈点有φ(a_i)=13(i为偶数且i∈[1，g-2])，φ(a_i)=14(i为奇数且i∈[1，g-2])，φ(a₀)=11，φ(a_g-1)=12. 对于内圈点有：当m为奇数时，φ(v_I^m)=8(I≡2(mod 3))，φ(v_I^m)=9(I≡1(mod 3))，φ(v_I^m)=10(I≡0(mod 3))，φ(v₁^m)=10；当m为偶数时，φ(v_I^m)=9(I≡2(mod 3))，φ(v_I^m)=10(I≡1(mod 3))，φ(v_I^m)=11(I≡0(mod 3))，φ(v₁^m)=11.

情形3  当p≡1(mod 3)时，定义P(n，k)的一个3-全染色f₃如下：f₃(e_i^m)=1(i≡0(mod 3))，f₃(e_i^m)=2(i≡1(mod 3))，f₃(e_i^m)=3(i≡2(mod 3))，f₃(a_ib_i)=2(i≡1(mod 3))，f₃(e_p-1^m)=3. 则φ(a_i)=7(i为偶数)，φ(a_i)=8(i为奇数). 对于内圈点有以下情形：当m为奇数时，φ(v_I^m)=8(I≡2(mod 3))，φ(v_I^m)=9(I≡1(mod 3))，φ(v_I^m)=10(I≡0(mod 3))，φ(v_p^m)=11；当m为偶数时，φ(v_I^m)=9(I≡2(mod 3))，φ(v_I^m)=10(I≡1(mod 3))，φ(v_I^m)=11(I≡0(mod 3))，φ(v_p^m)=12.

引理3  当n为奇数时，fgndi_Σ(P(n，k))≤3.

证  令e_i⁰=a_ia_i+1，i∈[0，n-1]. 设f为P(n，k)的一个3-全染色，具体染色情况如下：

情况1  对外圈染色：(ⅰ)当n$ \not \equiv$2(mod 3)时，令f(a_i)=1，f(b_i)=3，f(e_i⁰)=1(i≡0(mod 3))，f(e_i⁰)=2(i≡2(mod 3))，f(e_i⁰)=3(i≡1(mod 3))；(ⅱ)当n≡2(mod 3)时，令f(a_i)=1，f(b_i)=3，f(e_i⁰)=1(i≡0(mod 3)且i＜n-5)，f(e_i⁰)=2(i≡2(mod 3)且i＜n-5)，f(e_i⁰)=3(i≡1(mod 3)且i＜n-5)，f(e_n-1⁰)=f(e_n-2⁰)=2，f(e_n-3⁰)=f(e_n-4⁰)=3，f(e_n-5⁰)=1.

情况2  对内圈染色：令f(a_i)=1，f(b_i)=3. (ⅰ)当p$ \not \equiv$2(mod 3)时，令f(e_i⁰)=1(i≡0(mod 3))，f(e_i⁰)=2(i≡1(mod 3))，f(e_i⁰)=3(i≡2(mod 3))；(ⅱ)当p≡2(mod 3)时，令f(e_i⁰)=1(i≡0(mod 3))，f(e_i⁰)=2(i≡1(mod 3))，f(e_i⁰)=3(i≡2(mod 3))，f(a_ib_i)=3(i∈[0，p-1]).

首先，考虑内圈为情况2(ⅱ)的情况，则外圈点的权重范围为[10, 13]，而内圈点的权重范围为[14, 16]，所以内外圈的相邻点权重不同. 由染色f得外圈点权重为：φ(a_i)=10(i≡0(mod 3))，φ(a_i)=11(i≡1(mod 3))，φ(a_i)=12(i≡2(mod 3)). 特殊地，对于情况1(ⅱ)有φ(a_n-3)=13，φ(a_n-2)=12，所以外圈相邻点权重不同. 其次，考虑内圈点的权重，同样不考虑情况2(ⅱ)，则有φ(v_I^m)=14(I≡2(mod 3))，φ(v_I^m)=15(I≡1(mod 3))，φ(v_I^m)=16(I≡0(mod 3))，所以内圈相邻点权重不同. 下面对情况2(ⅱ)进行分析：当内圈出现情况2(ⅱ)时，令f(a_ib_i)=3，i∈[0，p-1]，此时与这p条边相连的内圈点比外圈点权重多2，而对于内圈相邻点来说，其权重差是1，因此染色后依旧是可区别的. 最后，外圈点在染色f下的权重分别按照如下规律：从a₀到a_p-1，依次为10，11，12，10，…，11，12，且φ(a_n-1)=11，则染色后各自权重变为12，13，14，12，…，13，14，且φ(a_n-1)=11，所以相邻点权重是可区别的. 特殊地，φ(a_p-1)和φ(a_p)未讨论，因为n为奇数，所以p，g也为奇数，只要染色前φ(a_p)比φ(a_p-1)恰好大2不成立，则染色后φ(a_p-1)+2≠φ(a_p)恒成立，根据前面讨论的权重规律，引理3得证.

2. 循环图

定义3  循环图C(n，l)(n≥3，1≤l≤$ \frac{2}{n}$)是由顶点集V={a₁，a₂，…，a_n}和边集E={a_ia_i+1，a_ia_i+l|i∈[1，n]}构成的一类正则图.

C(n，l)具有以下性质：(a) g=gcd(n，l)；(b)$ p = \frac{g}{n}$，其中g表示外圈C=a₁a₂…a_na₁内部所包含的不交圈的个数，且每个不交圈的长度均为p；(c) 当$ l = \frac{n}{2}$时，C(n，l)为三正则图，其他情形时为四正则图.

定理2  当n为偶数，l为奇数或n=2l时，fgndi_Σ(C(n，l))=2；当n为奇数，l为偶数或$ l = \left\lfloor {\frac{n}{2}} \right\rfloor $时，fgndi_Σ(C(n，l))≤3.

由定义3知C(n，l)是正则图，则fgndi_Σ(C(n，l))≥2. 定理2分以下4个引理证明：

引理4  当n为偶数，l为奇数时，fgndi_Σ(C(n，l))=2.

证  定义C(n，l)的一个2-全染色f如下：f(a_ia_i+1)=f(a_ia_i+l)=1，f(a_i)=2(i≡1(mod 2)). 由染色f可得C(n，l)中各点的权重为：φ(a_i)=10(i≡0(mod 2))，φ(a_i)=13(i≡1(mod 2))，证毕.

引理5  当n为奇数，l为偶数时，fgndi_Σ(C(n，l))≤3.

证  定义e_i^m=a_ia_i+l，i∈[1，p-1]，l∈[1，g]. 便于叙述，把顶点a_i按内圈个数g重新依次标号为v_I^m，I∈[1，p]，m∈[1，g]. 如C(20，4)包含4个不交圈，每个圈长度为5，那么原来的点a₁，a₅，a₉，a₁₃，a₁₇转变为点v₁¹，v₂¹，v₃¹，v₄¹，v₅¹，点a₂，a₆，a₁₀，a₁₄，a₁₈转变为点v₁²，v₂²，v₃²，v₄²，v₅²等等，依次类推. C(n，l)的一个3-全染色f如下：f(a_i)=3(i≡0(mod 2)).

情形1  当p≠2(mod 3)时，f(e_i^m)=1(i≡1(mod 3))，f(e_i^m)=2(i≡2(mod 3))，f(e_i^m)=3(i≡0(mod 3)). 则当m为奇数时，φ(v_i^m)=14(i≡1(mod 3))，φ(v_i^m)=16(i≡2(mod 3))，φ(v_i^m)=15(i≡0(mod 3))；当m为偶数时，φ(v_i^m)=16(i≡1(mod 3))，φ(v_i^m)=18(i≡2(mod 3))，φ(v_i^m)=17(i≡0(mod 3)). 若存在φ(a_i)=φ(a_i-1)=16，将边a_ia_i+1重染为3，则a_i与a_i+1的权重分别在原来基础上增加2，而a_i-1的权重并未改变，所以a_i-1与a_i的权重不同. 特殊地，当p≡1(mod 3)且i=p时有φ(v_p^m)=13.

情形2  当p≡2(mod 3)时，若i∈[1，p-2]，则染色规则与情形1相同，且有f(e_p-1^m)=2，f(e_p^m)=3. 由此可得，当i∈[1，p-3]时各点的权重同情形1；当i∈[p-2，p]时，若m为奇数，则φ(v_p^m)=15，φ(v_p-1^m)=16，φ(v_p-2^m)=17，若m为偶数，则φ(v_p^m)=17，φ(v_p-1^m)=18，φ(v_p-2^m)=19. 若存在φ(a_i)=φ(a_i-1)，则此时调色方案同情形1.

引理6  当n为奇数，$ l = \left\lfloor {\frac{n}{2}} \right\rfloor $时，fgndi_Σ(C(n，l))≤3.

证  令e_i^′=a_ia_i+l，i∈[1，p-1]. 定义$ C\left( {n, \left\lfloor {\frac{n}{2}} \right\rfloor } \right)$的一个3-全染色f如下：

情形1  当p≡0(mod 3)时，令f(e_i^′)=1(i≡1(mod 3))，f(e_i^′)=2(i≡2(mod 3))，f(e_i^′)=3(i≡0(mod 3))，则φ(a_i)=11(i≡1(mod 3))，φ(a_i)=10(i≡2(mod 3))，φ(a_i)=12(i≡0(mod 3)).

情形2  当p≡1(mod 3)时，染色规则同情形1，则φ(a₁)=9. 当1＜i≤$ \frac{{n + 1}}{2}$时，φ(a_i)=10(i≡1(mod 3))，φ(a_i)=12(i≡2(mod 3))，φ(a_i)=11(i≡0(mod 3))；当$ \frac{{n + 3}}{2}$≤i≤n时，φ(a_i)=12(i≡1(mod 3))，φ(a_i)=11(i≡2(mod 3))，φ(a_i)=10(i≡0(mod 3)).

情形3  当p≡2(mod 3)时，f(e_p-1^′)=2，f(e_p^′)=f(a₁a₂)=3. 当1≤i≤p-2时，f(e_i^′)=3(i≡1(mod 3))，f(e_i^′)=1(i≡2(mod 3))，f(e_i^′)=2(i≡0(mod 3))，则φ(a₁)=15，φ(a₂)=13；当3≤i≤$ \frac{{n + 1}}{2}$时，φ(a_i)=10(i≡1(mod 3))，φ(a_i)=12(i≡2(mod 3))，φ(a_i)=11(i≡0(mod 3))，φ ($ {a_{\frac{{n + 3}}{2}}}$) =12；当$ \frac{{n + 5}}{2}$≤i≤n时，φ(a_i)=11(i≡1(mod 3))，φ(a_i)=10(i≡2(mod 3))，φ(a_i)=12(i≡0(mod 3)).

引理7  当n=2l时，fgndi_Σ(C(n，l))=2.

证  令e_i^′=a_ia_i+l，i∈[1，l]. 设f为$ C\left( {n, \frac{n}{2}} \right)$的一个2-全染色，f定义如下：

情形1  当l＞5时，若l为奇数，令f(a_1+l)=f(e_i^′)=2(i=1，3，…，l-4)，f(a_1+la_2+l)=f(a_1+la_l)=f(a_ia_i+1)=2(i=3，5，…，l-4)，则φ(a₂)=φ(a_n)=φ(a_l-2)=7，φ(a_l)=φ(a_l+2)=9，

若l为偶数，令f(a_1+l)=f(e_i^′)=2(i=1，4，6，8，…，l-2)，f(a_ia_i+1)=2(i=3，5，…，l-1或i=4+l，6+l，…，2l-2)，则φ(a₂)=φ(a_n)=φ(a_l+3)=7，φ(a₁)=9，φ(a₃)=8，φ(a_1+l)=11，

情形2  当l=3时，令f(a₁a₄)=f(a₃a₄)=f(a₄a₅)=f(a₄)=2，得φ(a₁)=φ(a₃)=φ(a₅)=9，φ(a₂)=φ(a₆)=7，φ(a₄)=11.

情形3  当l=4时，令f(a₁a₅)=f(a₃a₇)=f(a₃a₄)=f(a₄a₅)=f(a₅a₆)=f(a₅)=2，得φ(a₁)=φ(a₃)=φ(a₆)=9，φ(a₂)=φ(a₈)=7，φ(a₄)=10，φ(a₅)=11，φ(a₇)=8.

情形4  当l=5时，令f(a₁a₆)=f(a₃a₈)=f(a₄a₉)=f(a₂a₃)=f(a₅a₆)=f(a₆a₇)=f(a₉a₁₀)=f(a₄)=2，得φ(a_i)=9(i=1，3，5，7，9)，φ(a₂)=φ(a₄)=φ(a₈)=φ(a₁₀)=8，φ(a₆)=11.

参考文献 (10)

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

[1]	KAROSKI M, ŁUCZAK T, THOMASON A. Edge Weights and Vertex Colours[J]. Journal of Combinatorial Theory(Series B), 2004, 91(1): 151-157. doi: 10.1016/j.jctb.2003.12.001
[2]	KALKOWSKI M, KAROSKI M, PFENDER F. Vertex-Coloring Edge-Weightings: Towards the 1-2-3-Conjecture[J]. Journal of Combinatorial Theory(Series B), 2010, 100(3): 347-349. doi: 10.1016/j.jctb.2009.06.002
[3]	ADDARIO-BERRY L, DALAL K, MCDIARMID C, et al. Vertex-Colouring Edge-Weightings[J]. Combinatorica, 2007, 27(1): 1-12. doi: 10.1007/s00493-007-0041-6
[4]	ADDARIO-BERRY L, DALAL K, REED B A. Degree Constrained Subgraphs[J]. Discrete Applied Mathematics, 2008, 156(7): 1168-1174. doi: 10.1016/j.dam.2007.05.059
[5]	WANG T, YU Q L. On Vertex-Coloring 13-Edge-Weighting[J]. Frontiers of Mathematics in China, 2008, 3(4): 581-587. doi: 10.1007/s11464-008-0041-x
[6]	PRZYBYŁO J. The 1-2-3 Conjecture Almost Holds for Regular Graphs[J]. Journal of Combinatorial Theory, Series B, 2021, 147: 183-200. doi: 10.1016/j.jctb.2020.03.005
[7]	PRZYBYŁO J, WOŹNIAK M. On a 1, 2 Conjecture[J]. Discrete Mathematics and Theoretical Computer Science, 2010, 12(1): 101-108.
[8]	KALKOWSKI M. A Note on the 1, 2-Conjecture[D]. Poznan: Adam Mickiewicz University, 2010.
[9]	FLANDRIN E, LI H, MARCZYK A. et al. A Note on Neighbor Expanded Sum Distinguishing Index[J]. Discussiones Mathematicae Graph Theory, 2017, 37(1): 29-37. doi: 10.7151/dmgt.1909
[10]	张辉, 李泽鹏, 陈祥恩. 仙人掌图的邻点被扩展和可区别全染色[J]. 高校应用数学学报, 2019, 34(3): 373-378. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-GXYZ201903012.htm

留言板