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

Abstract: An -labeling of a graph is an assignment of nonnegative integers to the vertices of such that if vertices and are adjacent, , and if and are at distance two, . The -number of is the minimum span over all -labelings of . A generalized Petersen graph (GPG) of order consists of two disjoint copies of cycles on 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. [Copyright &y& Elsevier]