Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7543496 | Discrete Optimization | 2016 | 10 Pages |
Abstract
Given a simple graph G, an L(2,1)-labelling (or λ-labelling) of G is a function c:V(G)âN such that |c(x)âc(y)|â¥2, if x and y are neighbors and |c(x)âc(y)|â¥1 if x and y have a common neighbor. The span of a labelling is the difference of the smallest and largest labels used. An L(2,1)-span of a graph G, denoted by λ(G), is a minimum span over all L(2,1)-labellings of G. The problem of determining if λ(G)â¤k is NP-Complete for any kâ¥4. In this paper, we obtain a linear time algorithm to compute λ(G) for any (q,qâ4)-graph with q fixed. Another important topic regarding the λ-labelling is to bound the λ-chromatic number of a graph by some function of it. Griggs and Yeh conjectured that λ(G)â¤Î2 for any graph G with maximum degree Îâ¥2. They also proved that the greedy algorithm for the problem uses at most Î2+Î. Furthermore we prove that the Griggs-Yeh conjecture is true for P4-sparse graphs, P4-laden graphs and all (q,qâ4)-graphs with at least 3q/2 vertices.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Márcia R. Cerioli, Nicolas A. Martins, Daniel F.D. Posner, Rudini Sampaio,