Abstract | ||
---|---|---|
An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208–223] conjectured that if G is an r-regular graph and ρ(G)⩾1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1016/j.dam.2007.07.009 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
05C15,05C78 | Journal | 155 |
Issue | ISSN | Citations |
17 | 0166-218X | 4 |
PageRank | References | Authors |
0.44 | 7 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sarah Spence Adams | 1 | 55 | 7.61 |
Matthew Tesch | 2 | 133 | 8.54 |
Denise Sakai Troxell | 3 | 76 | 9.24 |
Bradford Westgate | 4 | 9 | 1.28 |
Cody Wheeland | 5 | 8 | 0.87 |