#### Document Type

Article

#### Department

â€‹Mathematics

#### Publication Date

2003

#### Abstract

For positive integers $j \geq k$, the $\lambda_{j,k}$-number of graph *G*is the smallest span among all integer labelings of *V*(*G*) such that vertices at distance two receive labels which differ by at least *k* and adjacent vertices receive labels which differ by at least *j*. We prove that the $\lambda_{j,k}$-number of any *r*-regular graph is no less than the $\lambda_{j,k}$-number of the infinite *r*-regular tree $T_{\infty}(r)$. Defining an *r*-regular graph *G* to be $(j,k,r)$-optimal if and only if $\lambda_{j,k}(G) = \lambda_{j,k}(T_{\infty}(r))$, we establish the equivalence between $(j,k,r)$-optimal graphs and *r*-regular bipartite graphs with a certain edge coloring property for the case ${j \over k} > r$. The structure of $r$-regular optimal graphs for ${j \over k} \leq r$ is investigated, with special attention to ${j \over k} = 1,2$. For the latter, we establish that a (2,1,*r*)-optimal graph, through a series of edge transformations, has a canonical form. Finally, we apply our results on optimality to the derivation of the $\lambda_{j,k}$-numbers of prisms.

## Comments

Originally published in

SIAM Journal of Discrete Math.17 (2003), pp. 320-331. http://dx.doi.org/10.1137/S0895480101391247Provided by the Trinity College Digital Repository in accordance with the publisher's archiving policies.