Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427708 | Information Processing Letters | 2012 | 5 Pages |
An L(2,1)L(2,1)-labeling of a graph G=(V,E)G=(V,E) is a function f:V(G)→{0,1,2,…}f:V(G)→{0,1,2,…} such that |f(u)−f(v)|⩾2|f(u)−f(v)|⩾2 whenever uv∈E(G)uv∈E(G) and |f(u)−f(v)|⩾1|f(u)−f(v)|⩾1 whenever u and v are at distance two apart. The span of an L(2,1)L(2,1)-labeling f of G , denoted as SP2(f,G)SP2(f,G), is the maximum value of f(x)f(x) over all x∈V(G)x∈V(G). The L(2,1)L(2,1)-labeling number of a graph G , denoted as λ(G)λ(G), is the least integer k such that G admits an L(2,1)L(2,1)-labeling of span k . The problem of computing λ(G)λ(G) of a graph is known to be NP-complete. Griggs and Yeh have conjectured that λ(G)⩽Δ2(G)λ(G)⩽Δ2(G) for a graph G with maximum degree, Δ(G)Δ(G), at least two. In this paper, we propose constant approximation algorithms for the problem of computing λ(G)λ(G) for dually chordal graphs and strongly orderable graphs. As a by-product, we prove Griggs and Yeh Conjecture for dually chordal graphs and for those strongly orderable graphs whose maximum degrees are different from three. Finally, we propose a 2-approximation algorithm for computing λ(G)λ(G) for chordal bipartite graphs, a special subclass of strongly orderable graphs, and prove that Griggs and Yeh Conjecture holds true for this class of graphs.
► We propose constant approximation algorithms for computing λ(G)λ(G) for dually chordal graphs. ► We propose constant approximation algorithms for computing λ(G)λ(G) for strongly orderable graphs. ► We prove Griggs and Yeh Conjecture for dually chordal graphs and for chordal bipartite graphs. ► We propose a 2-approximation algorithm for computing λ(G)λ(G) for chordal bipartite graphs. ► We prove Griggs and Yeh Conjecture for strongly orderable graphs for which Δ≠3Δ≠3.