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,\ldots,m-1\}\) such that \(|f(u)-f(v)|_m \geq j\) if \(u\) and \(v\) are adjacent, and \(|f(u)-f(v)|_m \geq 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'(j,k)\)-labelling is a one-to-one \(L(j,k)\)-labelling, and the \(m\)-\((j,k)’\)-circular labelling is a one-to-one \(m\)-\((j,k)\)-circular labelling. Denote \(\lambda’_{j,k}(G)\) the \(L'(j,k)\)-labelling number and \(\sigma’_{j,k}(G)\) the \(m\)-\((j,k)’\)-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}\)-number of Cartesian products of complete graphs [J Comb Optim (2007) 14: 219-227].