For a connected graph G of graph diameter d, the distance-k graph G_k for k = 1, ..., d is a graph with the same vertex set and having edge set consisting of the pairs of vertices that lie a distance k apart. It is therefore the case that G_1 = G. Distance graphs of interest (because they are distance-regular) include the distance-2 graphs of the Gosset graph, Hoffman-Singleton graph, and Klein graph and the distance-3 graphs of the Heawood graph (quartic vertex-transitive graph Qt31) and 6-folded cube graph.

distance graph | graph neighborhood | halved graphs | local graph | neighborhood graph