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

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

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

Shuangliang Tian ^1, , Ping Chen ^2, , Yabin Shao ^1, and Qian Wang ^1,

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

Abstract
Related Papers

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: adjacent vertex distinguishing edge-coloring, Cartesian product., total-coloring, adjacent vertex distinguishing total-coloring, Edge-coloring.

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

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 and 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-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.

show all references

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.

[1]	Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, Anand Srivastav. Price of anarchy for graph coloring games with concave payoff. Journal of Dynamics and Games, 2017, 4 (1) : 41-58. doi: 10.3934/jdg.2017003
[2]	Sudeb Majee, Subit K. Jain, Rajendra K. Ray, Ananta K. Majee. A fuzzy edge detector driven telegraph total variation model for image despeckling. Inverse Problems and Imaging, 2022, 16 (2) : 367-396. doi: 10.3934/ipi.2021054
[3]	Klaus-Jochen Engel, Marjeta Kramar Fijavž, Rainer Nagel, Eszter Sikolya. Vertex control of flows in networks. Networks and Heterogeneous Media, 2008, 3 (4) : 709-722. doi: 10.3934/nhm.2008.3.709
[4]	Monika Muszkieta. A variational approach to edge detection. Inverse Problems and Imaging, 2016, 10 (2) : 499-517. doi: 10.3934/ipi.2016009
[5]	Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2020, 14 (4) : 573-577. doi: 10.3934/amc.2020030
[6]	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
[7]	Kengo Matsumoto. On the Markov-Dyck shifts of vertex type. Discrete and Continuous Dynamical Systems, 2016, 36 (1) : 403-422. doi: 10.3934/dcds.2016.36.403
[8]	Chris Bernhardt. Vertex maps for trees: Algebra and periods of periodic orbits. Discrete and Continuous Dynamical Systems, 2006, 14 (3) : 399-408. doi: 10.3934/dcds.2006.14.399
[9]	Klaus-Jochen Engel, Marjeta Kramar Fijavž. Waves and diffusion on metric graphs with general vertex conditions. Evolution Equations and Control Theory, 2019, 8 (3) : 633-661. doi: 10.3934/eect.2019030
[10]	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
[11]	Liming Zhang, Tao Qian, Qingye Zeng. Edge detection by using rotational wavelets. Communications on Pure and Applied Analysis, 2007, 6 (3) : 899-915. doi: 10.3934/cpaa.2007.6.899
[12]	Qilin Wang, Shengji Li, Kok Lay Teo. Continuity of second-order adjacent derivatives for weak perturbation maps in vector optimization. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 417-433. doi: 10.3934/naco.2011.1.417
[13]	Moussa Doumbia, Abdul-Aziz Yakubu. Malaria incidence and anopheles mosquito density in irrigated and adjacent non-irrigated villages of Niono in Mali. Discrete and Continuous Dynamical Systems - B, 2017, 22 (3) : 841-857. doi: 10.3934/dcdsb.2017042
[14]	Yuying Shi, Ying Gu, Li-Lian Wang, Xue-Cheng Tai. A fast edge detection algorithm using binary labels. Inverse Problems and Imaging, 2015, 9 (2) : 551-578. doi: 10.3934/ipi.2015.9.551
[15]	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
[16]	David Henry, Octavian G. Mustafa. Existence of solutions for a class of edge wave equations. Discrete and Continuous Dynamical Systems - B, 2006, 6 (5) : 1113-1119. doi: 10.3934/dcdsb.2006.6.1113
[17]	Fahe Miao, Michal Fečkan, Jinrong Wang. Exact solution and instability for geophysical edge waves. Communications on Pure and Applied Analysis, 2022, 21 (7) : 2447-2461. doi: 10.3934/cpaa.2022067
[18]	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
[19]	Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems and Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191
[20]	Lu Yang, Guangsheng Wei, Vyacheslav Pivovarchik. Direct and inverse spectral problems for a star graph of Stieltjes strings damped at a pendant vertex. Inverse Problems and Imaging, 2021, 15 (2) : 257-270. doi: 10.3934/ipi.2020063

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Shuangliang Tian Ping Chen Yabin Shao Qian Wang
on Google Scholar
Shuangliang Tian Ping Chen Yabin Shao Qian Wang

[Back to Top]