Constructing status injective graphs

Abstract

The status, or distance sum, of a given vertex v in a graph is defined by s(v) = ∑_(u ≠ v)d(u, v) where d(u, v) is the distance from a vertex u to v. We show that every graph is the induced subgraph of a graph whose vertices all have distinct stati. Using this result we then construct a family of graphs which have consecutive integers for their stati. This settles the question raised by Harary and Buckley about whether there exist graphs whose stati are consecutive integers. We also use the above constructions to find families of non-isomorphic graphs with the same stati.

Additional details