Edge Labelings with a Condition at Distance Two

Xuexiang Sun, Wensong Lin, and Zengmin Song
Department of Mathematics, Southeast University, Nanjing 210096, P. R. China


Abstract     Full Text  PDF

For positive integers $j$ and $k$, $j\geq k$, a $(j,k)$-edge labeling of a graph $G$ is an assignment of nonnegative integers to $E(G)$ such that the difference between labels of adjacent edges is at least $j$, and the difference between labels of edges that are distance two apart is at least $k$. The $\lambda_{j,k}^{'}$-number of $G$ is the minimum span taken over all $(j,k)$-edge labelings of $G$. In this paper, we obtain bounds on $\lambda_{2,1}^{'}(G)$ and $\lambda_{1,1}^{'}(G)$ for some classes of graphs, including unit interval graphs, the Cartesian product of two paths, graphs with the maximum degree of its line graph, and some "cycle-tree".