Publication details
Construction of large graphs with no optimal surjective L(2,1)-labelings
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | SIAM Journal on Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1137/050623061 |
| Keywords | channel assignment problem; graph labeling with distance conditions |
| Description | An L(2, 1)-labeling of a graph G is a mapping c : V (G) --> {0,..., K} such that the labels of two adjacent vertices differ by at least two and the labels of vertices at distance two differ by at least one. A hole of c is an integer h. {0,..., K} that is not used as a label for any vertex of G. The smallest integer K for which an L(2, 1)-labeling of G exists is denoted by lambda(G). The minimum number of holes in an optimal labeling, i.e., a labeling with K = lambda(G), is denoted by rho(G). Georges and Mauro [SIAM J. Discrete Math., 19 ( 2005), pp. 208 - 223] showed that rho(G) <= Delta, where Delta is the maximum degree of G, and conjectured that if.( G) =. and G is connected, then the order of G is at most Delta(Delta+1). We disprove this conjecture by constructing graphs G with rho(G) = Delta and order [(Delta+1)(2)/4] (Delta+ 1) approximate to Delta(3)/4. |