Graph Distance Graph

Author

Eric W. Weisstein
July 18, 2025

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/GraphDistanceGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/GraphDistanceGraph.html.

©2025 Wolfram Research, Inc. except for portions noted otherwise

Figure

<<MathWorld`Graphs`

GraphicsGrid[
{
Annotate[GraphData[#],PlotLabel->GraphData[#,"Name"]],
GraphDistanceGraph[GraphData[#],2,PlotLabel->"distance 2\[Hyphen]graph of the "<>GraphData[#,"Name"]]
}&/@{"KleinGraph24"}//StyleGraphs,
BaseStyle->InsetBoxOptions->{BaseStyle->Directive[LightDarkSwitched@Black,14,Italic,FontFamily->"Times"]}
]

Table

<<MathWorld`Graphs`

RecognizeGraph/@Table[RandomGraph[{n,Floor[Binomial[n,2]/2]}],{n,8,10}]

Families

TextGrid[With[{gs=SortBy[GraphData["Antiprism"],GraphData[#,"V"]&]},
DeleteCases[{
#,
1+Flatten@Position[Table[IsomorphicGraphQ[g=GraphData[#],GraphDistanceGraph[g,n]],{n,2,20}],True]}&/@gs,
{_,{}}]],Dividers->All]

TextGrid[With[{gs=SortBy[GraphData["Caveman"],GraphData[#,"V"]&]},
DeleteCases[{
#,
1+Flatten@Position[Table[IsomorphicGraphQ[g=GraphData[#],GraphDistanceGraph[g,n]],{n,2,20}],True]}&/@gs,{_,{}}]],Dividers->All]

TextGrid[With[{gs=SortBy[GraphData["Cycle"],GraphData[#,"V"]&]},
DeleteCases[{
#,
1+Flatten@Position[Table[IsomorphicGraphQ[g=GraphData[#],GraphDistanceGraph[g,n]],{n,2,20}],True]}&/@gs,{_,{}}]],Dividers->All]

TextGrid[With[{gs=SortBy[GraphData["Hypercube"],GraphData[#,"V"]&]},
DeleteCases[{
#,
1+Flatten@Position[Table[IsomorphicGraphQ[g=GraphData[#],GraphDistanceGraph[g,n]],{n,2,20}],True]}&/@gs,{_,{}}]],Dividers->All]

TextGrid[With[{gs=SortBy[GraphData["Prism"],GraphData[#,"V"]&]},
DeleteCases[{
#,
1+Flatten@Position[Table[IsomorphicGraphQ[g=GraphData[#],GraphDistanceGraph[g,n]],{n,2,20}],True]}&/@gs,{_,{}}]],Dividers->All]

TextGrid[With[{gs=SortBy[GraphData["Sunlet"],GraphData[#,"V"]&]},
DeleteCases[{
#,
1+Flatten@Position[Table[IsomorphicGraphQ[g=GraphData[#],GraphDistanceGraph[g,n]],{n,2,20}],True]}&/@gs,{_,{}}]],Dividers->All]

TextGrid[With[{gs=SortBy[GraphData["TorusGrid"],GraphData[#,"V"]&]},
DeleteCases[{
#,
1+Flatten@Position[Table[IsomorphicGraphQ[g=GraphData[#],GraphDistanceGraph[g,n]],{n,2,20}],True]}&/@gs,{_,{}}]],Dividers->All]

Distance-2

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],2]],60]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-3

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],3]],60]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-4

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],4]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-5

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],5]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-6

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],6]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-7

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],7]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-8

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],8]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-9

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],9]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-10

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],10]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-11

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],11]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-12

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],12]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-13

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],13]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-14

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],14]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-15

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],15]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-16

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],16]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-17

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],17]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-18

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],18]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-19

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],19]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-20

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],20]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-21

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],21]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-22

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],22]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]

Distance-23

data=Monitor[DeleteCases[{
g=#,
TimeConstrained[RecognizeGraph[GraphDistanceGraph[GraphData[#],23]],5]
}&/@GraphData[All],
{_,{}}
],
g];//Timing

Cases[
data,
{gn_,$Aborted}:>gn
]

Distance graph is isomorphic to itself

Cases[data,{x_,x_}:>x]

Distance graph is a string in GraphData

nice=Cases[
data,
{_,_String?(GraphData[#,"Connected"]&)}
];

nice[[All,2]]//Union

TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Reverse/@nice,First],First],Dividers->All]