#### Title

On Island Sequences of Labelings with a Condition at Distance Two

#### Abstract

An *L(2,1)-labeling* of a graph *G *is a function *f* from the vertex set of *G* to the set of nonnegative integers such that |*f(x)* – *f(y)| ≥ *2 if *d(x,y) *= 1, and |*f(x)* –* f(y)| *≥ 1 if *d(x,y) *= 2,* *where* d(x,y) *denotes the distance between the pair of vertices* x, y*. The *lambda number* of *G*, denoted *l**(G),* is the minimum range of labels used over all L(2,1)-labelings of *G*. An L(2,1)-labeling of *G* which achieves the range *l**(G) *is referred to as a *l*-labeling. A *hole* of an L(2,1)-labeling is an unused integer within the range of integers used. The *hole index* of *G, *denoted *r**(G), *is the minimum number of holes taken over all its *l*-labelings. An *island* of a given *l*-labeling of *G* with *r**(G) *holes is a maximal set of consecutive integers used by the labeling. Georges and Mauro [*SIAM J.* *Discrete Math.*, 19 (2005), page 211] inquired about the existence of a connected graph *G* with *r**(G) *≥ 1 possessing two *l*-labelings with different ordered sequences of island cardinalities. This paper provides an infinite family of such graphs together with their lambda numbers and hole indices. Key to our discussion is the path covering number of certain *2-sparse graphs,* that is, graphs containing no pair of adjacent vertices of degree greater than 2.

#### Academic Division

Math/Science

#### Disciplines

Discrete Mathematics and Combinatorics

#### Recommended Citation

Troxell, Denise Sakai; Adams, Sarah Spence; Trazkovich, Alex; and Westgate, Bradford, "On Island Sequences of Labelings with a Condition at Distance Two" (2009). *Babson Faculty Research Fund Working Papers*. 40.

https://digitalknowledge.babson.edu/bfrfwp/40

## Comments

For full text, please see

Discrete Applied Mathematics, Volume 158, Issue 1, 6 January 2010, Pages 1-7;doi: http://dx.doi.org/10.1016/j.dam.2009.08.005