The Δ 2 -conjecture for L(2, 1)-labelings is true for direct and strong products of graphs.
Sandi Klavžar, Simon Špacapan · IEEE Transactions on Circuits & Systems II Express Briefs · 2006
A variation of the channel assignment problem is naturally modeled by L(2, 1)-labelings of graphs. An L(2, 1)-labeling of a graph G is an assignment of labels from {0, 1, . . . , λ} to the vertices of G such that vertices at distance two get different labels and adjacent vertices get labels that are at least two apart and the λ-number λ(G) of G is the minimum value λ such that G admits an L(2, 1)-labeling. The ∆-conjecture asserts that for any graph G its λ-number is at most the square of its largest degree. In this paper it is shown that the conjecture holds for graphs that are direct or strong products of nontrivial graphs. Explicit labelings of such graphs are also constructed.