تعداد نشریات | 45 |
تعداد شمارهها | 1,080 |
تعداد مقالات | 8,960 |
تعداد مشاهده مقاله | 8,109,308 |
تعداد دریافت فایل اصل مقاله | 6,240,930 |
Adjacent vertex distinguishing acyclic edge coloring of the Cartesian product of graphs | ||
Transactions on Combinatorics | ||
مقاله 7، دوره 6، شماره 2، تابستان 2017، صفحه 19-30 اصل مقاله (495.24 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22108/toc.2017.20988 | ||
نویسندگان | ||
Fatemeh Sadat Mousavi ![]() | ||
University of Zanjan | ||
چکیده | ||
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)$. | ||
کلیدواژهها | ||
Acyclic edge coloring؛ adjacent vertex distinguishing acyclic edge coloring؛ adjacent vertex distinguishing acyclic edge chromatic number | ||
مراجع | ||
[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. | ||
آمار تعداد مشاهده مقاله: 699 تعداد دریافت فایل اصل مقاله: 592 |