For a connected graph G of graph diameter d, the graph 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 graph distance k apart. It is therefore the case that G_1 = G . Graph distance graphs differ from Euclidean distance graphs in that the former are constructed based on graph distance between vertices, while the latter are constructed based on Euclidean distance. Special classes of graphs isomorphic to their own graph k-distance graph are summarized in the table below.
