An L(2,1)-labeling of a graph G is an assignment f of nonnegative integers to the vertices of G such that if vertices x and y are adjacent, |f(x)−f(y)|≥2, and if x and y are at distance two, |f(x)−f(y)|≥1. The λ-number of Gis the minimum span over all L(2,1)-labelings of G. A generalized Petersen graph (GPG) of order n consists of two disjoint copies of cycles on n vertices together with a perfect matching between the two vertex sets. By presenting and applying a novel algorithm for identifying GPG-specific isomorphisms, this paper provides exact values for the λ-numbers of all GPGs of orders 9, 10, 11, and 12. For all but three GPGs of these orders, the λ-numbers are 5 or 6, improving the recently obtained upper bound of 7 for GPGs of orders 9, 10, 11, and 12. We also provide the λ-numbers of several infinite subclasses of GPGs that have useful representations on Möbius strips.
- L(2,
- 1)-labeling; L(2,
- 1)-coloring; Distance two labeling; Graph labeling; Channel assignment; Generalized Petersen graph
Available at: http://works.bepress.com/sarah_spence_adams/24/
© 2012 Elsevier. This article was published in Discrete Applied Mathematics, vol. 160, iss. 4-5, pg. 436-447 and may be found here.