Neighbor full sum distinguishing total coloring of two types of Cartesian product graphs

YE Hongbo; YANG Chao; YIN Zhixiang; YAO Bing

doi:10.12299/jsues.21-0252

Volume 35 Issue 1

Sep. 2022

Turn off MathJax

Article Contents

Article Navigation > Journal of Shanghai University of Engineering Science > 2022 > 36(1): 91-97

YE Hongbo, YANG Chao, YIN Zhixiang, YAO Bing. Neighbor full sum distinguishing total coloring of two types of Cartesian product graphs[J]. Journal of Shanghai University of Engineering Science, 2022, 36(1): 91-97. doi: 10.12299/jsues.21-0252

Citation:

YE Hongbo, YANG Chao, YIN Zhixiang, YAO Bing. Neighbor full sum distinguishing total coloring of two types of Cartesian product graphs[J]. Journal of Shanghai University of Engineering Science, 2022, 36(1): 91-97. doi: 10.12299/jsues.21-0252

Citation:

PDF( 680 KB)

Neighbor full sum distinguishing total coloring of two types of Cartesian product graphs

doi: 10.12299/jsues.21-0252

YE Hongbo^{1a
,},
YANG Chao^{1a, 1b
,
,},
YIN Zhixiang^{1a, 1b},
YAO Bing²

1a.
a. School of Mathematics, Physics and Statistics; b. Center of Intelligent Computing and Applied Statistics, Shanghai University of Engineering Science, Shanghai 201620, China
1b.
Center of Intelligent Computing and Applied Statistics, Shanghai University of Engineering Science, Shanghai 201620, China
2.
College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

Received Date: 2021-11-14
Publish Date: 2022-09-26

Abstract

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.

FullText(HTML)

References(9)

References

[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