Adjacent vertex distinguishing  edge-colorings and total-colorings  of   the Cartesian product of graphs

Shuangliang Tian; Ping Chen; Yabin Shao; Qian Wang

doi:10.3934/naco.2014.4.49

Article Contents

2014, Volume 4, Issue 1: 49-58. Doi: 10.3934/naco.2014.4.49

This issue Previous Article Some useful inequalities via trace function method in Euclidean Jordan algebras Next Article Grasping force based manipulation for multifingered hand-arm Robot using neural networks

Adjacent vertex distinguishing edge-colorings and total-colorings of the Cartesian product of graphs

1.
College of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030
2.
College of Management, Northwest University for Nationalities, Lanzhou 730030

Received: March 2013

Revised: November 2013

Published: December 2013

Abstract / Introduction Related Papers Cited by

Abstract

Let $G$ be a simple graph with vertex set $V(G)$ and edge set $E(G)$. An edge-coloring $\sigma$ of $G$ is called an adjacent vertex distinguishing edge-coloring of $G$ if $F_{\sigma}(u)\not= F_{\sigma}(v)$ for any $uv\in E(G)$, where $F_{\sigma}(u)$ denotes the set of colors of edges incident with $u$. A total-coloring $\sigma$ of $G$ is called an adjacent vertex distinguishing total-coloring of $G$ if $S_{\sigma}(u)\not= S_{\sigma}(v)$ for any $uv\in E(G)$, where $S_{\sigma}(u)$ denotes the set of colors of edges incident with $u$ together with the color assigned to $u$. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring (resp. an adjacent vertex distinguishing total-coloring) of $G$ is denoted by $\chi_a^{'}(G)$ (resp. $\chi^{''}_{a}(G)$). In this paper, we provide upper bounds for these parameters of the Cartesian product $G$ □ $H$ of two graphs $G$ and $H$. We also determine exact value of these parameters for the Cartesian product of a bipartite graph and a complete graph or a cycle, the Cartesian product of a complete graph and a cycle, the Cartesian product of two trees and the Cartesian product of regular graphs.

Keywords:

Edge-coloring,
total-coloring,
adjacent vertex distinguishing edge-coloring,
adjacent vertex distinguishing total-coloring,
Cartesian product.

Mathematics Subject Classification: Primary: 05C35, 05C75; Secondary: 05C60.

Citation:

Related Papers

Cited by

References

[1]	S. Akbari, H. Bidkhori and N. Nosrati, r-Strong edge colorings of graphs, Discrete Math., 306 (2006), 3005-3010.doi: 10.1016/j.disc.2004.12.027.
[2]	P. N. Balister, E. Győri, J. Lehel and R. H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math., 21 (2007), 237-250.doi: 10.1137/S0895480102414107.
[3]	J-L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes, Australasian Journal of Combinatorics, 35 (2006), 89-102.
[4]	J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976.
[5]	M. Chen and X. Guo, Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes, Information Processing Letters, 109 (2009), 599-602.doi: 10.1016/j.ipl.2009.02.006.
[6]	K. Edwards, M. Horňák and M. Woźniak, On the neighbor-distinguishing index of a graph, Graphs Combin., 22 (2006), 341-350.doi: 10.1007/s00373-006-0671-2.
[7]	H. Hatami, ∆+300 is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory Ser. B, 95 (2005), 246-256.doi: 10.1016/j.jctb.2005.04.002.
[8]	S. Tian and P. Chen, On adjacent vertex-distinguishing total coloring of two classes of product graphs, Journal of Mathematical Research and Exposition, 27 (2007), 733-737.
[9]	H. Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with ∆(G)=3, Journal of Combinatorial Optimization, 14 (2007), 87-109.doi: 10.1007/s10878-006-9038-0.
[10]	H. P. Yap, Total Coloring of Graph, Springer Verlag, New York, 1996.
[11]	Z. Zhang, X. Chen, J. Li, B. Yao, X. Lu and J. Wang, On adjacent-vertex-distinguishing total coloring of graphs, Science in China Series A, Mathematics, 48 (2005), 289-299.doi: 10.1360/03YS0207.
[12]	Z. Zhang, L. Liu and J. Wang, Adjacent strong edge coloring of graphs, Applied Mathematics Letters, 15 (2002), 623-626.doi: 10.1016/S0893-9659(02)80015-5.