Graph Distance Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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 (Brouwer et al. 1989, p. 437).

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.

condition distance-k graph is isomorphic to itself

k>1 (3k-1)-antiprism graph

k>1 odd (k,3)-caveman graph

k>1 odd prism graph P_2 square C_(2k)

k>1 odd 2(k-1)-sunlet graph

k>1 torus grid graph C_(n+1) square C_(n+1)

k>2 odd hypercube graph Q_(n+1)

Notable graphs that are isomorphic to their own distance-k graph are summarized in the following table.

k graph and distance-k graphs are isomorphic

2 generalized quadrangle GQ(2,1), icosahedral graph, Paley graphs, Peisert graphs

3 Franklin graph, Hoffman graph, Pasch graph, rhombic dodecahedral graph, Wells graph