`a`
Numerical Algebra, Control and Optimization (NACO)
 

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

Pages: 49 - 58, Volume 4, Issue 1, March 2014      doi:10.3934/naco.2014.4.49

 
       Abstract        References        Full Text (347.3K)       Related Articles       

Shuangliang Tian - College of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, China (email)
Ping Chen - College of Management, Northwest University for Nationalities, Lanzhou 730030, China (email)
Yabin Shao - College of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, China (email)
Qian Wang - College of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, China (email)

Abstract: 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:  Edge-coloring, total-coloring, adjacent vertex distinguishing edge-coloring, adjacent vertex distinguishing total-coloring, Cartesian product.
Mathematics Subject Classification:  Primary: 05C35, 05C75; Secondary: 05C60.

Received: March 2013;      Revised: November 2013;      Available Online: December 2013.

 References