Advances in Applied Mathematics
Vol.
09
No.
08
(
2020
), Article ID:
37275
,
5
pages
10.12677/AAM.2020.98159
Strict Neighbor-Distinguishing Total Coloring of Subcubic Graphs
Hanquan Liu, Jing Gu
College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua Zhejiang
Received: Aug. 3rd, 2020; accepted: Aug. 19th, 2020; published: Aug. 26th, 2020
ABSTRACT
A proper total k-coloring of a graph G is a mapping , such that any two adjacent or incident elements in receive different colors. Let Cφ(v) be the set of colors assigned to a vertex v and those edges incident to v. φ is strict neighbor-distinguishing if and for each edge . The strict neighbor-distin- guishing total index, denoted by χsnt(G), of G is the minimum integer k such that G is k-strict neighbor-distinguishing total colorable. In this paper, we prove that every subcubic graph G has .
Keywords:Strict Neighbor-Distinguishing Total Coloring, Strict Neighbor-Distinguishing Total Index, Subcubic Graphs
子立方图的严格邻点可区别全染色
刘含荃,顾静
浙江师范大学数学与计算机科学学院,浙江 金华
收稿日期:2020年8月3日;录用日期:2020年8月19日;发布日期:2020年8月26日
摘 要
图G的一个正常k-全染色是指一个映射 ,使得 中任意两个相邻的或相关联的元素染不同颜色。令Cφ(v)表示点v的颜色与v的关联边的颜色组成的集合。如果满足对任意一条边 都有和 ,则称φ是k-严格邻点可区别的。图G的严格邻点可区别全色数是使G是k-严格邻点可区别全可染的最小正整数k,用χsnt(G)表示。本文证明了每个子立方图满足 。
关键词 :严格邻点可区别全染色,严格邻点可区别全色数,子立方图
Copyright © 2020 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本文只考虑有限简单图,设G是一个点集为V(G),边集为E(G)的图,它的最大度,最小度分别为Δ(G),δ(G)。当点v的度是k时,称为k-点。令NG(v)代表与v相邻的点集。很容易得到对简单图G中的任一点v,有 。在不会混淆的情况下,Δ(G),δ(G),dG(v)和NG(v)分别可以写成Δ,δ,d(v)和N(v)。令Pn和Cn分别表示阶为n的路和阶为n的圈。如果图G的每个点的度都是一个固定的常数k,则称G是k-正则的。一个图G如果是3-正则的,则称为立方图;如果满足 ,则称为子立方图。图G如果满足 ,则称G为正常的。
图G的一个正常k-全染色是指一个映射 ,使得对任意两个相邻的或相关联的元素 ,有 。设 。如果对任意一对相邻的点u和v,有 ,我们把φ称为邻点可区别的。图G的邻点可区别全色数Xat(G)是使G有一个k-邻点可区别全染色的最小正整数k。此外,如果对任意一对相邻的点u和V,有 和 ,我们称φ为严格邻点可区别的。图G的严格邻点可区别全色数χat(G)是使G有一个k-严格邻点可区别全染色的最小正整数k。
2005年,张忠辅等人在 [1] 中首先给出了图的邻点可区别全染色的概念,并且对圈、完全图、完全二部图、扇、轮图和树的邻点可区别全染色展开研究,确定了它们的邻点可区别全色数,并根据特殊图的邻点可区别全色数提出了如下猜想:
猜想1 [1] 对于阶不少于2的简单连通图G,有 。
如果猜想1成立,则这个上界是紧的。例如,对于任意正整数 ,有 。Chen和Wang分别在 [2] 和 [3] [4] 中证明了 的连通图满足猜想1。奇数阶的完全图的邻点可区别全色数可以达到猜想1的上界,由于奇数阶的完全图的最大度为偶数,但是对于 的连通图,上界6是否是紧的这一问题至今仍未解决。Papaioannou和Raftopoulou在 [5] 中从算法的角度证明了所有的4-正则图G,有 ,是满足猜想1的。Lu等人在 [6] 中运用组合零点定理证明了所有 的连通图G,有 ,是满足猜想1的。Huang,Wang和Yan在 [7] 中把 的图的邻点可区别全色数的上界改进到2Δ(G)。
严格邻点可区别全染色(被命名为Smarandachely邻点可区别全染色)有及以下猜想。
猜想2 对于阶不小于2的简单连通图G,有 。
2009年,梁少卫在 [8] 中证明了 的k-正则偶图和k-方体图Qk,满足猜想2。2011年,卫斌等人在 [9] 中证明了圈的平方图,满足猜想2。文献 [10] [11] [12] [13] 中给出了若干类的3-正则图的严格邻点可区别全色数均为5,满足猜想2。2015年,陈妹君等人在 [14] 中研究了Mycielski图的严格邻点可区别全色数满足猜想2。2019年,李春梅等人在 [15] 证明了 的2-连通外平面图满足猜想2。
2. 主要结果
在展示主要结果前,我们先建立一些有用的观察。首先,根据定义,以下式子显然成立。
引理1 [2] 如果图G是一个 的图,则G有一个6-邻点可区别全染色。
引理2 对 ,每个r-正则图G满足 。
结合引理1和2,我们得到以下事实:
引理3 如果图G是一个3-正则图,则 。
引理4 对一个阶为n的圈Cn,有 。
引理5 对 ,有 。
证明:设 ,连接v1和vn得到一个圈Cn。设 是一个颜色集合。由引理4,Cn有一个4-严格邻点可区别全染色φ。除了点v1和vn,用与Cn相同的颜色染Pn中的点和边,设 ,,用α染点v1,用β染点vn。 £
定理1 如果图G是一个正常的子立方图,则 。
证明:我们用反证法证明。设 是一个颜色集合。假设图G是一个边数 最小的极小反例。如果 ,则定理成立,因为足以给每条边分配不同的颜色。所以假设G是一个 , 的图,且G无法用C中的颜色染好。
如果 ,G是一个圈或一条路,由引理4和引理5,有 。所以假设 。为了完成证明,我们需要构造以下一系列的断言。在断言的证明中,我们用C(v)代替Cφ(v)。
断言1 G不包含1-点。
证明:反之,G包含一个1-点v。设点u是v的邻点。如果 ,设 ;如果 ,设 。令 ,则H是一个 且 的图。所以H存在一个6-严格邻点可区别全染色φ,其所用颜色集合为C。
对 ,如果 ,取 。令 ,用α染边uv。令 ,用β染点v。断言1的证明完成。 £
断言2 G不包含相邻2-点。
证明:反之,G包含两个相邻2-点u和v。设 ,。令 ,则H是一个 且 的图。所以H存在一个6-严格邻点可区别全染色φ,其所用颜色集合为C。
先假设 。己知 ,令 ,用α改染点v。令 ,用β染边uv。因此 。如果 ,令 ,用α改染点v。令 ,用β染边uv。如果 ,令 ,用β染边uv。断言2的证明完成。 £
断言3 G中的3-点不与3个2-点相邻。
证明:反之,v是G中的3-点, 且 。由断言2,u,x,y两两不相邻。令 ,则H是一个 的图。所以H存在一个6-严格邻点可区别全染色φ,其所用颜色集合为C。
情形1. 。
令 ,用α染点v。集合C\{α}中必定存在一个在C(u),C(x),C(y)中至多用了一次的颜色,不妨设为1。
如果 ,用1染边uv。令 ,用β1染边vx。当 ,因为 ,令 ,用β2染边vy。当 ,删去边uv的颜色,用1染边vy。设 ,。如果 ,取 ,因为 ,令 ,用β2染边uv。
如果 (或C(x),或C(y)),假设 。用1染边vx,因为 ,令 ,用β1染边vy。设 ,。如果 ,取 ,因为 ,令 ,用β2染边uv。
情形2. 。
设 ,则 。因为 ,令 ,用α改染点u。此时 ,根据情形1,G有一个6-严格邻点可区别全染色。
断言3的证明完成。 £
断言4 G中2-点不与3-点相邻。
证明:反之,G包含相邻的3-点u和2-点v,设 ,因此w是一个3-点。设 , 。u1,u2,w1,w2是2-点或3-点。由断言3,u1或u2是3-点,w1或w2是3-点。不妨设 ,。令 ,则H是一个 的图。所以H存在一个6-严格邻点可区别全染色φ,其所用颜色集合为C。如果 ,取 。如果 ,取 。设 。
情形1. 。
设 ,用α1染边uv。设 ,用α2染边vw。设 ,用α3染点v。
情形2. 。
不妨设 。令 ,,用α1染边uv,α2染边vw。如果 ,令 ,用α3染点v。如果 ,令 ,用α3染点v。
情形3. 。
不妨设 。令 ,,用α1染边uv,α2染边vw,6染点v。
情形4. 。
不妨设 ,。删去点w的颜色,用4染边vw。当 时,取 。当 时,取 。令 ,用α1染点w。显然, 。令 ,,用α2染边uv,α3染点v。
断言4的证明完成。 £
由断言1-4得G是3-正则的。但是根据引理3,G有一个6-严格邻点可区别全染色的,矛盾。 £
文章引用
刘含荃,顾 静. 子立方图的严格邻点可区别全染色
Strict Neighbor-Distinguishing Total Coloring of Subcubic Graphs[J]. 应用数学进展, 2020, 09(08): 1346-1350. https://doi.org/10.12677/AAM.2020.98159
参考文献
- 1. Zhang, Z., Chen, X., Li, J., Yao, B., Lu, X. and Wang, J. (2005) On Adjacent-Vertex-Distinguishing Total Coloring of Graphs. Science in China Series A, 48, 289-299. https://doi.org/10.1360/03YS0207
- 2. Chen, X. (2008) On the Adjacent Vertex Distinguishing Total Coloring Numbers of Graphs with Δ = 3. Discrete Mathematics, 308, 4003-4007. https://doi.org/10.1016/j.disc.2007.07.091
- 3. Wang, H. (2007) On the Adjacent Vertex-Distinguishing Total Chromatic Numbers of the Graphs with Δ(G) = 3. Journal of Combinatorial Optimization, 14, 87-109. https://doi.org/10.1007/s10878-006-9038-0
- 4. Hulgan, J. (2009) Concise Proofs for Adjacent Vertex-Distinguishing Total Colorings. Discrete Mathematics, 309, 2548-2550. https://doi.org/10.1016/j.disc.2008.06.002
- 5. Papaioannou, A. and Raftopoulou, C. (2014) On the AVDTC of 4-Regular Graphs. Discrete Mathematics, 330, 20-40. https://doi.org/10.1016/j.disc.2014.03.019
- 6. Lu, Y., Li, J., Luo, R. and Miao, Z. (2017) Adjacent Vertex Distinguishing Total Coloring of Graphs with Maximum Degree 4. Discrete Mathematics, 340, 119-123. https://doi.org/10.1016/j.disc.2016.07.011
- 7. Huang, D., Wang, W. and Yan, C. (2012) A Note on the Adjacent Vertex Distinguishing Total Chromatic Number of Graphs. Discrete Mathematics, 312, 3544-3546. https://doi.org/10.1016/j.disc.2012.08.006
- 8. 梁少卫. k-方体图的Smarandachely邻点全染色[J]. 唐山学院学报, 2009, 22(3): 6-7.
- 9. 卫斌, 朱恩强, 文飞, 徐文辉. 圈的平方图的Smarandachely邻点全色数[J]. 惠州学院学报(自然科学版), 2011, 31(6): 13-15.
- 10. Li, J., Wang, Z., Wen, F. and Zhang, Z. (2010) The Smarandachely Adjacent-Vertex Distinguishing Total Coloring of Two Kind of 3-Regular Graphs. 3rd International Conference on Biomedical Engineering and Informatics, Yantai, 16-18 October 2010, 3004-3006. https://doi.org/10.1109/BMEI.2010.5639827
- 11. 时亭亭, 强会英, 文飞. 广义拟Thomassen图的Smarandachely邻点全色数[J]. 兰州交通大学学报, 2010, 29(4): 147-149.
- 12. Wang, Z., Lee, J., Li, J. and Wen, F. (2011) The Smarandachely Adjacent Vertex Total Coloring of a Kind of 3-Regular Graph. Ars Combinatoria, 99, 45-53.
- 13. 李沐春, 王立丽, 张伟东, 凌昭昭. 若干类3-正则图的Smarandachely邻点全染色的界[J]. 南开大学学报(自然科学版), 2014, 47(6): 79-84.
- 14. 陈妹君, 田双亮. 两类运算图的Smarandachely邻点可区别全染色[J]. 贵州师范大学学报(自然科学版), 2015, 33(1): 73-75.
- 15. 李春梅, 王治文. Δ(G) ≤ 3的2-连通外平面图的Smarandachely邻点可区别全色数[J]. 大学数学, 2019, 35(3): 1-4.