Neighbor full sum distinguishing total coloring of two types of Cartesian product graphs
-
摘要:
设
\begin{document}$f:V(G) \cup E(G) \to \{ 1, 2,\cdots , k\}$\end{document} 是图G的一个正常k−全染色，令权重
$\phi (x) = f(x) + \mathop \Sigma \limits_{e \mathrel\backepsilon x} f(e) + \mathop \Sigma \limits_{y \in N(x)} f(y)$ ，其中
$ N(x) = \{ y \in V(G)|xy \in E(G)\} $ . 对任意的边
$ uv \in E(G) $ ，如果有
$\phi (u) \ne \phi (v)$ 成立，则称
$ f $ 为图
$ G $ 的一个邻点全和可别正常k正常k−全染色. 图G的邻点全和可区别全色数是指对图
$ G $ 进行邻点全和可区别k−全染色所需要的最小色数k，记为
${\rm{ftnd}}{{\rm{i}}_\Sigma }(G)$ . 本研究猜想：对于最大度为
$ \Delta $ 的图
$ G $ (
$ {K_2} $ 除外)，
${\rm{ftnd}}{{\rm{i}}_\Sigma }(G) \leqslant \Delta + 2$ . 研究得到路与路的笛卡尔乘积图和路与圈的笛卡尔乘积图的邻点全和可区别全色数均为
$ \Delta + 1 $ ，证实了上述猜想.
-
关键词:
- 正常全染色 /
- 邻点全和可区别全染色 /
- 邻点全和可区别全色数
Abstract:Let
\begin{document}$f:V(G) \cup E(G) \to \{ 1,2,\cdots ,k\}$\end{document} be a proper
k-total coloring of a graph G. Define a weight function on total coloring as
$ \phi (x) = f(x) + \mathop \Sigma \limits_{e \mathrel\backepsilon x} f(e) + \mathop \Sigma \limits_{y \in N(x)} f(y) $ , where
$ N(x) = \{ y \in V(G)|xy \in E(G)\} $ . If
$ \phi (u) \ne \phi (v) $ for any edge
$ uv \in E(G) $ , then f is called a neighbor full sum distinguishing k-total coloring of G. The smallest value k for which G admins a neighbor full sum distinguishing total coloring with k colors is called the neighbor full sum distinguishing total chromatic number of G and denoted by
${\rm{ftnd}}{{\rm{i}}_\Sigma }(G)$ . The research conjectures that
${\rm{ftnd}}{{\rm{i}}_\Sigma }(G) \leqslant \Delta + 2$ for every graph except for
$ {K_2} $ , where ∆ represents the maximum degree of G. Meanwhile, we get this parameter for Cartesian product graphs of paths and paths, paths and cycles are ∆ + 1, respectively, which confirm the above conjecture.
-
[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: The MaCmillan Press ltd., 1976. [2] FLANDRIN E, MARCZYK A, PRZYBYLO J, et al. Neighbor sum distinguishing index[J] . Graphs and Combinatorics,2013,29(5):1329 − 1336. [3] PILSNIAK M, WOZNIAK M. On the total-neighbor-distinguishing index by sums[J] . Graphs and Combinatorics,2015,31(3):771 − 782. [4] DONG A J, WANG G H. Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree[J] . Acta Mathematica Sinica (English Series),2014,30(4):703 − 709. doi: 10.1007/s10114-014-2454-7 [5] LI H L, DING L H, LIU B Q, et al. Neighbor sum distinguishing total colorings of planar graphs[J] . Journal of Combinatorial Optimization,2015,30(3):675 − 688. doi: 10.1007/s10878-013-9660-6 [6] WANG G H, YAN G Y. An improved upper bound for the neighbor sum distinguishing index of graphs[J] . Discrete Applied Mathematics,2014,175:126 − 128. doi: 10.1016/j.dam.2014.05.013 [7] VIZING V G. On an estimate of the chromatic class of a p-graph[J] . Diskret Analiz,1964,3(1):25 − 30. [8] BEHZAD M. Graphs and their chromatic numbers[D]. East Lansing: Michigan State University, 1965. [9] ZHANG Z F, CHEN X E, LI J W, et al. On adjacent- vertex-distinguishing total coloring of graphs[J] . Science in China Series A: Mathematics,2005,48(3):289 − 299. doi: 10.1360/03YS0207 -
点击查看大图
计量
- 文章访问数: 301
- HTML全文浏览量: 170
- PDF下载量: 49
- 被引次数: 0
下载:
