On real number labelings and graph invertibility

Abstract

For non-negative real x(0) and simple graph G, lambda(x0.1) (G) is the minimum span over all labelings that assign real numbers to the vertices of G such that adjacent vertices receive labels that differ by at least x(0) and vertices at distance two receive labels that differ by at least 1. In this paper, we introduce the concept of lambda-invertibility: G is lambda-invertible if and only if for all positive x, lambda(x,1)(G) = x lambda(1/x,1) (G(c)). We explore the conditions under which a graph is lambda-invertible, and apply the results to the calculation of the function lambda(x,1)(G) for certain lambda-invertible graphs G. We give families of lambda-invertible graphs, including certain Kneser graphs, line graphs of complete multipartite graphs, and self-complementary graphs. We also derive the complete list of all lambda-invertible graphs with maximum degree 3. (C) 2012 Elsevier B.V. All rights reserved.