Relationships Between Distance-Two Labellings and Circular Distance-Two Labellings by Group Path Covering

Abstract

For positive integers $j$ and $k$ with $j>k$, an $L(j,k)$-labelling is a generalization of classical graph coloring where adjacent vertices are assigned integers at least $j$ apart, and vertices at distance two are assigned integers at least $k$ apart. The span of an $L(j,k)$-labelling of a graph $G$ is the difference between the maximum and minimum integers assigned to its vertices. The $L(j,k)$-labelling number of $G$, denoted by ${\lambda }_{j,k}(G)$, is the minimum span over all $L(j,k)$-labellings of $G$. An $m$-$(j,k)$-circular labelling of $G$ is a function $f:V(G)\to \{0,1,\dots ,m-1\}$ such that $|f(u)-f(v){|}_m\ge j$ if $u$ and $v$ are adjacent, and $|f(u)-f(v){|}_m\ge k$ if $u$ and $v$ are at distance two, where $|x{|}_m=min\{|x|,m-|x|\}$. The span of an $m$-$(j,k)$-circular labelling of $G$ is the difference between the maximum and minimum integers assigned to its vertices. The $m$-$(j,k)$-circular labelling number of $G$, denoted by ${\sigma }_{j,k}(G)$, is the minimum span over all $m$-$(j,k)$-circular labellings of $G$. The $L^{\prime }(j,k)$-labelling is a one-to-one $L(j,k)$-labelling, and the $m$-$(j,k{)}^{\prime }$-circular labelling is a one-to-one $m$-$(j,k)$-circular labelling. Denote ${\lambda }_{j,k}^{\prime }(G)$ the $L^{\prime }(j,k)$-labelling number and ${\sigma }_{j,k}^{\prime }(G)$ the $m$-$(j,k{)}^{\prime }$-circular labelling number. When $j=d,k=1$, $L(j,k)$-labelling becomes $L(d,1)$-labelling. [Discrete Math. 232 (2001) 163-169] determined the relationship between ${\lambda }_{2,1}(G)$ and ${\sigma }_{2,1}(G)$ for a graph $G$. We generalized the concept of path covering to the $t$-group path covering (Inform Process Lett (2011)) of a graph. In this paper, using group path covering, we establish relationships between ${\lambda }_{4,1}(G)$ and ${\sigma }_{4,1}(G)$ and between ${\lambda }_{j,k}(G)$ and ${\sigma }_{j,k}(G)$ for a graph $G$ with diameter 2. Using these results, we obtain shorter proofs for the ${\sigma }_{j,k}^{\prime }$-number of Cartesian products of complete graphs [J Comb Optim (2007) 14: 219-227].