06030946

j

06030946 Wang, Feng Lin, Wensong Group path covering and $L(j,k)$-labelings of diameter two graphs. Inf. Process. Lett. 112, No. 4, 124-128 (2012). 2012 Elsevier Sciences Publishers (North-Holland), Amsterdam EN $L(j k)$-labeling path covering $\lfloor $j/k$\rfloor $-group path coverings Cartesian products of complete graphs direct products of complete graphs combinatorial problems Zbl 0811.05058 Zbl 0966.05070 Zbl 1132.05053

doi:10.1016/j.ipl.2011.11.005

Summary: $L(j,k)$-labeling is a kind of generalization of the classical graph coloring motivated from a kind of frequency assignment problem in radio networks, in which adjacent vertices are assigned integers that are at least $j$ apart, while vertices that are at distance two are assigned integers that are at least $k$ apart. The span of an $L(j,k)$-labeling of a graph $G$ is the difference between the maximum and the minimum integers assigned to its vertices. The $L(j,k)$-labeling number of $G$, denoted by $\lambda _{j,k}(G)$, is the minimum span over all $L(j,k)$-labelings of {\it G. Georges}, {\it D. W. Mauro} and {\it M. Whittlesey} [Discrete Math. 135, No. 1--3, 103--111 (1994; Zbl 0811.05058)] established the relationship between $\lambda_{2,1}(G)$ of a graph $G$ and the path covering number of $G^c$ (the complement of G). {\it G. Georges}, {\it D. W. Mauro} and {\it M. I. Stein} [SIAM J. Discrete Math. 14, No. 1, 28--35 (2001; Zbl 0966.05070 )] determined the $L(j,k)$-labeling numbers of Cartesian products of two complete graphs. {\it P. C. B. Lam}, {\it W. Lin} and {\it J.Wu} [J. Comb. Optim. 14, No. 2--3, 219--227 (2007; Zbl 1132.05053)] determined the $\lambda_{ j,k}$-numbers of direct products of two complete graphs. In 2011, the authors [Inf. Process. Lett. 111, 621--625 (2011)] generalized the concept of the path covering to the t-group path covering of a graph where $t(\ge 1)$ is an integer and established the relationship between the $L'(d,1)$-labeling number $(d\geq 2)$ of a graph $G$ and the $(d - 1)$-group path covering number of $G^c$. In this paper, we establish the relationship between the $\lambda_{j,k}(G)$ of a graph $G$ with diameter 2 and the $\lfloor j/k\rfloor$ -group path coverings of $G^c$. Using those results, we can have shorter proofs to obtain the $\lambda _{j,k}$ of the Cartesian products and direct products of complete graphs.