Neighbor Full Sum Distinguishing Total Coloring of Two Types of Regular Graphs

定义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得证.

定义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.