Distance k-Graph

Author

Eric W. Weisstein
January 24, 2009

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Distancek-Graph.nb.

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

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

Table

l=Monitor[DeleteCases[{g=#,RecognizeGraph[TimeConstrained[DistanceGraph[Graph[#],2],5]]}&/@Take[GraphData[All],All],{_,{}}],g];//Timing

TableForm[DeleteCases[l,{_,{"Empty",_}|{_Integer,_Integer}|$Aborted}],TableDepth->2]

Special Cases

With[{g="KleinGraph"},{Diameter[Graph[g]],RecognizeGraph[DistanceGraph[Graph[g],#]]&/@Range[3]}]

With[{g="HoffmanSingletonGraph"},{Diameter[Graph[g]],RecognizeGraph[DistanceGraph[Graph[g],#]]&/@Range[3]}]

GraphData[#,"DeterminedBySpectrum"]&/@{"KleinDistance2Graph","HoffmanSingletonComplementGraph"}

With[{g="GrayGraph"},{Diameter[Graph[g]],RecognizeGraph[DistanceGraph[Graph[g],#]]&/@Range[3]}]

RecognizeGraph[DistanceGraph[Graph["TruncatedIcosahedralGraph"],2]]

Figure

New

GraphicsGrid[{GraphPlot[Graph[#],Method->None,PlotLabel->GraphData[#,"Name"]],GraphPlot[DistanceGraph[Graph[#],2],Method->None,PlotLabel->"distance 2-graph of the "<>GraphData[#,"Name"],"EdgeColor"->Directive[AbsoluteThickness[.2]]]}&/@{"KleinGraph"},ImageSize->400,Spacings->{-50,-10},BaseStyle->Italic]

Original

GraphicsGrid[{GraphPlot[Graph[#],Method->None,PlotLabel->GraphData[#,"Name"]],GraphPlot[DistanceGraph[Graph[#],2],Method->None,PlotLabel->"distance 2-graph of the "<>GraphData[#,"Name"],"EdgeColor"->Directive[AbsoluteThickness[.2]]]}&/@{"HoffmanSingletonGraph","KleinGraph"},ImageSize->400,Spacings->{-50,-10},BaseStyle->{FontSlant->"Italic"}]