Exact λ-numbers of generalized Petersen graphs of certain higher-orders and on Möbius strips

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 G is 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.