Back to Search
Start Over
On the hole index of L(2,1)-labelings of r-regular graphs
- Source :
-
Discrete Applied Mathematics . Oct2007, Vol. 155 Issue 17, p2391-2393. 3p. - Publication Year :
- 2007
-
Abstract
- 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 , is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted , is the minimum number of holes taken over all L(2,1)-labelings with span exactly . 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 , then must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that and r are relatively prime integers. [Copyright &y& Elsevier]
- Subjects :
- *GRAPH theory
*ALGEBRA
*COMBINATORICS
*GRAPHIC methods
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 155
- Issue :
- 17
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 26835190
- Full Text :
- https://doi.org/10.1016/j.dam.2007.07.009