Document Type
Article
Department
​Mathematics
Publication Date
2003
Abstract
For positive integers $j \geq k$, the $\lambda_{j,k}$-number of graph Gis 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/S0895480101391247
Provided by the Trinity College Digital Repository in accordance with the publisher's archiving policies.