Adjacent vertex distinguishing acyclic edge coloring of the Cartesian product of graphs

Document Type : Research Paper

Authors

University of Zanjan

Abstract

‎Let $G$ be a graph and $\chi^{\prime}_{aa}(G)$ denotes the minimum number of colors required for an‎ ‎acyclic edge coloring of $G$ in which no two adjacent vertices are incident to edges colored with the same set of colors‎. ‎We prove a general bound for $\chi^{\prime}_{aa}(G\square H)$ for any two graphs $G$ and $H$‎. ‎We also determine‎ ‎exact value of this parameter for the Cartesian product of two paths‎, ‎Cartesian product of a path and a cycle‎, ‎Cartesian product of two trees‎, ‎hypercubes‎. ‎We show that $\chi^{\prime}_{aa}(C_m\square C_n)$ is at most $6$ fo every $m\geq 3$ and $n\geq 3$‎. ‎Moreover in some cases we find the exact value of $\chi^{\prime}_{aa}(C_m\square C_n)$‎.

Keywords

Main Subjects

References

[1] D. Amar, A. Raspaud and O. Togni, All-to-all wavwlength-routing in all-optical comp ound networks, Discrete Math., 235 (2001) 353-363.
[2] P. N. Balister, E. Gyori, J. Lehel and R. H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math., 21 (2007) 237-250.
[3] J. L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes, Australas. J. Combin., 35 (2006) 89-102.
[4] X. S. Liu, M. Q. An and Y. Gao, An upp er b ound for the adjacent vertex distinguishing acyclic edge chromatic numb er of a graph, Acta Math. Appl. Sin. Engl. Ser., 25 (2009) 137-140.
[5] W. C. Shiu, W. H. Chan, Z. F. Zhang and L. Bian, On the adjacent vertex-distinguishing acyclic edge coloring of some graphs, Appl. Math. J. Chinese Univ. Ser. B., 26 (2011) 439-452.
[6] J. J. Sylverster, Mathematical questions with their solutions, in: the Educational Times, 41, Francis Ho dgson, London, 1884 171-178.
[7] S. Tian, P. Chen, Y. Shao and Q. Wang, Adjacent vertex distinguishing edge-colorings and total colorings of the Cartesian pro duct of graphs, Numer. Algebra Control Optim., 4 (2014) 49-58.
[8] Z. F. Zhang, L. Z. Liu and J. F. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15 (2002) 623-626.

Files

History

  • Receive Date: 13 January 2016
  • Revise Date: 04 October 2016
  • Accept Date: 08 November 2016
  • Published Online: 01 June 2017

Share

How to cite

Statistics