    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:
  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  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  J-L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes,, Australasian Journal of Combinatorics, 35 (2006), 89. Google Scholar  J. A. Bondy and U. S. R. Murty, Graph Theory with Applications,, American Elsevier, (1976). Google Scholar  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  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  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  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  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  H. P. Yap, Total Coloring of Graph,, Springer Verlag, (1996). Google Scholar  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  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:
  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  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  J-L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes,, Australasian Journal of Combinatorics, 35 (2006), 89. Google Scholar  J. A. Bondy and U. S. R. Murty, Graph Theory with Applications,, American Elsevier, (1976). Google Scholar  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  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  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  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  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  H. P. Yap, Total Coloring of Graph,, Springer Verlag, (1996). Google Scholar  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  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
  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  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  Monika Muszkieta. A variational approach to edge detection. Inverse Problems & Imaging, 2016, 10 (2) : 499-517. doi: 10.3934/ipi.2016009  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  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  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  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  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  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  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  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  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  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  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  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  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  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  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  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  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: