Generalized vertex labelings with a condition at distance two. (English) Zbl 0904.05077

Georges, John P.; Mauro, David W.

Congr. Numerantium 109, 141-159 (1995).

Summary: An \(L(2,1)\)-labeling of graph \(G\) is an integer labeling of the vertices of \( G\) such that adjacent vertices receive labels which differ by at least 2, and vertices that are two apart receive labels which differ by at least 1. The \(\lambda\)-number of \(G\) is the minimum span over the \(L(2,1)\)-labelings of \(G\). In this paper, we investigate the analogously-defined \(L (j,k)\)-labelings of \(G\) for positive integers \(j\geq k\). We derive bounds for \(\lambda^j_k (G)\) in terms of various graph invariants, and we obtain exact expressions for the \(\lambda^j_k\)-numbers of cycles, paths, complete multipartite graphs, and \(t\)-point suspensions of paths and cycles. We also investigate the \(\lambda^j_k\)-numbers of trees and products of paths.

MSC:

05C78

Graph labelling (graceful graphs, bandwidth, etc.)

Keywords:

integer labeling; graph invariants; cycles; paths