Generalized Petersen graphs admit proper total colorings with four distinguishing constraints
-
摘要: 关于图的可区别染色的研究起源于移动通信的频率分配问题. 本文定义了简单图G的一个4-邻点可区别全染色. 对一个图G进行 4-邻点可区别全染色所需的最少颜色数称为图G的 4-邻点可区别全色数, 记为~$\chi^{\prime\prime}_{4as}(G)$. 对于广义~Petersen~图~$P(n,k)$, $6\leq \chi^{\prime\prime}_{4as} (P(n,k))\leq 7$ 得到证明.
-
关键词:
- 全染色 /
- 点可区别全染色 /
- 广义~Petersen~图
Abstract: The study of distinguishing coloring in graphs is derived from the frequency assignment problem in mobile communications. This paper introduced the concept of $4$-adjacent vertex distinguishing total coloring ($4$-avdtc) of a simple graph $G$. The minimum number of $k$ colors required for $G$ such that it satisfies a $4$-avdtc is denoted as $\chi^{\prime\prime}_{4as}(G)$. For generalized Petersen graphs $P(n,k)$, it was proved that $6\leq \chi^{\prime\prime}_{4as}(P(n,k))\leq 7$. -
[1] {1} BURRIS A C, SCHELP R H. Vertex-distinguishing proper edge-coloring[J]. J Graph Theory, 1997, 26(2): 70-82.{2} ZHANG Z F, LIU L Z, WANG J F. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, {15(5)}: 623-626.{3} VIZING V G. Some unsolved problems in graph theory[J]. Uspekhi Mat Nauk, {1968, 23: 117-134}.{4} BEHZAD M. Graphs and their chromatic numbers[D]. Michigan: Michigan State University, 1965.{5} ZHANG Z F, CHEN X E, LI J W, et al. On the adjacent vertex-distinguishing total coloring of graphs[J]. Science in China Series A.Mathematics(Chinese), 2004, {34(5)}: 574-583.{6} BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York: Macmillan Press, 1976.{7} WANG L W. On adjacent vertex distinguishing total coloring of generalized Petersen Graph[J]. ShanDong Science, 2007, {20(6)}: 4-8. -
点击查看大图
计量
- 文章访问数: 1465
- HTML全文浏览量: 33
- PDF下载量: 1947
- 被引次数: 0
下载: