# American Institute of Mathematical Sciences

2014, 4(1): 49-58. doi: 10.3934/naco.2014.4.49

## 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, China, China, China 2 College of Management, Northwest University for Nationalities, Lanzhou 730030, China

Received  March 2013 Revised  November 2013 Published  December 2013

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.
Citation: Shuangliang Tian, Ping Chen, Yabin Shao, Qian Wang. Adjacent vertex distinguishing edge-colorings and total-colorings of the Cartesian product of graphs. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 49-58. doi: 10.3934/naco.2014.4.49
##### References:
 [1] S. Akbari, H. Bidkhori and N. Nosrati, r-Strong edge colorings of graphs,, Discrete Math., 306 (2006), 3005. doi: 10.1016/j.disc.2004.12.027. Google Scholar [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. doi: 10.1137/S0895480102414107. Google Scholar [3] J-L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes,, Australasian Journal of Combinatorics, 35 (2006), 89. Google Scholar [4] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications,, American Elsevier, (1976). Google Scholar [5] M. Chen and X. Guo, Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes,, Information Processing Letters, 109 (2009), 599. doi: 10.1016/j.ipl.2009.02.006. Google Scholar [6] K. Edwards, M. Horňák and M. Woźniak, On the neighbor-distinguishing index of a graph,, Graphs Combin., 22 (2006), 341. doi: 10.1007/s00373-006-0671-2. Google Scholar [7] H. Hatami, ∆+300 is a bound on the adjacent vertex distinguishing edge chromatic number,, J. Combin. Theory Ser. B, 95 (2005), 246. doi: 10.1016/j.jctb.2005.04.002. Google Scholar [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. Google Scholar [9] H. Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with ∆(G)=3,, Journal of Combinatorial Optimization, 14 (2007), 87. doi: 10.1007/s10878-006-9038-0. Google Scholar [10] H. P. Yap, Total Coloring of Graph,, Springer Verlag, (1996). Google Scholar [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, 48 (2005), 289. doi: 10.1360/03YS0207. Google Scholar [12] Z. Zhang, L. Liu and J. Wang, Adjacent strong edge coloring of graphs,, Applied Mathematics Letters, 15 (2002), 623. doi: 10.1016/S0893-9659(02)80015-5. Google Scholar

show all references

##### References:
 [1] S. Akbari, H. Bidkhori and N. Nosrati, r-Strong edge colorings of graphs,, Discrete Math., 306 (2006), 3005. doi: 10.1016/j.disc.2004.12.027. Google Scholar [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. doi: 10.1137/S0895480102414107. Google Scholar [3] J-L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes,, Australasian Journal of Combinatorics, 35 (2006), 89. Google Scholar [4] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications,, American Elsevier, (1976). Google Scholar [5] M. Chen and X. Guo, Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes,, Information Processing Letters, 109 (2009), 599. doi: 10.1016/j.ipl.2009.02.006. Google Scholar [6] K. Edwards, M. Horňák and M. Woźniak, On the neighbor-distinguishing index of a graph,, Graphs Combin., 22 (2006), 341. doi: 10.1007/s00373-006-0671-2. Google Scholar [7] H. Hatami, ∆+300 is a bound on the adjacent vertex distinguishing edge chromatic number,, J. Combin. Theory Ser. B, 95 (2005), 246. doi: 10.1016/j.jctb.2005.04.002. Google Scholar [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. Google Scholar [9] H. Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with ∆(G)=3,, Journal of Combinatorial Optimization, 14 (2007), 87. doi: 10.1007/s10878-006-9038-0. Google Scholar [10] H. P. Yap, Total Coloring of Graph,, Springer Verlag, (1996). Google Scholar [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, 48 (2005), 289. doi: 10.1360/03YS0207. Google Scholar [12] Z. Zhang, L. Liu and J. Wang, Adjacent strong edge coloring of graphs,, Applied Mathematics Letters, 15 (2002), 623. doi: 10.1016/S0893-9659(02)80015-5. Google Scholar
 [1] Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, Anand Srivastav. Price of anarchy for graph coloring games with concave payoff. Journal of Dynamics & Games, 2017, 4 (1) : 41-58. doi: 10.3934/jdg.2017003 [2] Klaus-Jochen Engel, Marjeta Kramar Fijavž, Rainer Nagel, Eszter Sikolya. Vertex control of flows in networks. Networks & Heterogeneous Media, 2008, 3 (4) : 709-722. doi: 10.3934/nhm.2008.3.709 [3] Monika Muszkieta. A variational approach to edge detection. Inverse Problems & Imaging, 2016, 10 (2) : 499-517. doi: 10.3934/ipi.2016009 [4] Kengo Matsumoto. On the Markov-Dyck shifts of vertex type. Discrete & Continuous Dynamical Systems - A, 2016, 36 (1) : 403-422. doi: 10.3934/dcds.2016.36.403 [5] Chris Bernhardt. Vertex maps for trees: Algebra and periods of periodic orbits. Discrete & Continuous Dynamical Systems - A, 2006, 14 (3) : 399-408. doi: 10.3934/dcds.2006.14.399 [6] Robert L. Griess Jr., Ching Hung Lam. Groups of Lie type, vertex algebras, and modular moonshine. Electronic Research Announcements, 2014, 21: 167-176. doi: 10.3934/era.2014.21.167 [7] Klaus-Jochen Engel, Marjeta Kramar Fijavž. Waves and diffusion on metric graphs with general vertex conditions. Evolution Equations & Control Theory, 2019, 8 (3) : 633-661. doi: 10.3934/eect.2019030 [8] Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020030 [9] Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2020, 14 (1) : 171-175. doi: 10.3934/amc.2020014 [10] Liming Zhang, Tao Qian, Qingye Zeng. Edge detection by using rotational wavelets. Communications on Pure & Applied Analysis, 2007, 6 (3) : 899-915. doi: 10.3934/cpaa.2007.6.899 [11] Heinz-Jürgen Flad, Gohar Harutyunyan. Ellipticity of quantum mechanical Hamiltonians in the edge algebra. Conference Publications, 2011, 2011 (Special) : 420-429. doi: 10.3934/proc.2011.2011.420 [12] Yuying Shi, Ying Gu, Li-Lian Wang, Xue-Cheng Tai. A fast edge detection algorithm using binary labels. Inverse Problems & Imaging, 2015, 9 (2) : 551-578. doi: 10.3934/ipi.2015.9.551 [13] David Henry, Octavian G. Mustafa. Existence of solutions for a class of edge wave equations. Discrete & Continuous Dynamical Systems - B, 2006, 6 (5) : 1113-1119. doi: 10.3934/dcdsb.2006.6.1113 [14] Qilin Wang, Shengji Li, Kok Lay Teo. Continuity of second-order adjacent derivatives for weak perturbation maps in vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 417-433. doi: 10.3934/naco.2011.1.417 [15] Moussa Doumbia, Abdul-Aziz Yakubu. Malaria incidence and anopheles mosquito density in irrigated and adjacent non-irrigated villages of Niono in Mali. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 841-857. doi: 10.3934/dcdsb.2017042 [16] Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems & Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191 [17] Zehui Shao, Huiqin Jiang, Aleksander Vesel. L(2, 1)-labeling of the Cartesian and strong product of two directed cycles. Mathematical Foundations of Computing, 2018, 1 (1) : 49-61. doi: 10.3934/mfc.2018003 [18] Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edge-dislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361-387. doi: 10.3934/jgm.2015.7.361 [19] Sergey V. Dmitriev, Asiya A. Nazarova, Anatoliy I. Pshenichnyuk, Albert M. Iskandarov. Dynamics of edge dislocation clusters interacting with running acoustic waves. Discrete & Continuous Dynamical Systems - S, 2011, 4 (5) : 1079-1094. doi: 10.3934/dcdss.2011.4.1079 [20] Angel Angelov, Marcus Wagner. Multimodal image registration by elastic matching of edge sketches via optimal control. Journal of Industrial & Management Optimization, 2014, 10 (2) : 567-590. doi: 10.3934/jimo.2014.10.567

Impact Factor: