Geodetic Graph

Author

Eric W. Weisstein
November 29, 2021

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

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

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

Relation to ShortestPathCountMatrix

Geodetic

ShortestPathCountMatrix[CycleGraph[5]]

1-IdentityMatrix[5]

Not geodetic

ShortestPathCountMatrix[CycleGraph[6]]

Figure

gs=Flatten[Partition[#,UpTo[5]]&/@DeleteCases[Table[Select[GraphData["Geodetic",5],{n,5}]],{}],1];

i=0;
GraphicsGrid[Map[Annotate[StyleGraphs[#,VertexSize->If[++i==1,.015,{"Scaled",.06}]]&@GraphData[r=RecognizeGraph[#]],{PlotLabel->TextCell[GraphData[r,"Name"],PageWidth->100],LabelStyle->Directive[Black,Italic,FontFamily->"Times"]}]&,gs,{2}],Dividers->{{Thick,{True},Thick},{{Thick},True,Thick}},ImageSize->500,Alignment->Center]

Counts

A337179

Table[Total[Boole[GeodeticGraphQ/@ConnectedGraphs[n]]],{n,10}]//Timing

Length/@Table[GraphData["Geodetic",n],{n,10}]

Classes

Intersection@@GraphData["Geodetic","Classes"]

GraphClassesThatAreClass["Geodetic"]

Complement[GraphClassesThatAreClass["Geodetic"],GraphClassesThatAreClass["Tree"]]

Classes

Compute

data=Monitor[{g=#,TimeConstrained[ShortestPathCountMatrix[GraphData[#]]==1-IdentityMatrix[GraphData[#,"V"]],2]}&/@GraphData[All],g];//Timing

l={#,{0,#2}}&@@@DeleteCases[data,{_,$Aborted}]

Cases[data,{g_,$Aborted}:>g]

todo={"BiggsSmithGraph",{"BipartiteKneser",{11,5}},{"BipartiteKneser",{12,4}},{"BipartiteKneser",{12,5}},{"Cage",{5,12}},{"Cage",{9,8}},{"Cage",{10,8}},{"Cage",{12,8}},{"Cage",{14,8}},{"CubeConnectedCycle",7},{"CubeConnectedCycle",8},{"Cubic",{12,53}},{"Cubic",{14,380}},"DeGreyGraph",{"DiagonalIntersection",13},{"DiagonalIntersection",14},{"Doob",{1,3}},{"Doob",{2,1}},{"FibonacciCube",14},{"FibonacciCube",15},"Foster090A","Foster758A","Foster762A","Foster774A","Foster776A","Foster784A","Foster784B","Foster794A","Foster798A","Foster798B","Foster800A","Foster806A","Foster806B","Foster816A","Foster816B","Foster816C","Foster816D","Foster816E","Foster816F","Foster816G","Foster816H","Foster816I","Foster818A","Foster824A","Foster832A","Foster834A","Foster840A","Foster840B","Foster842A","Foster854A","Foster854B","Foster864A","Foster864B","Foster864C","Foster864D","Foster866A","Foster872A","Foster878A","Foster880A","Foster880B","Foster880C","Foster882A","Foster882B","Foster888A","Foster888B","Foster896A","Foster896B","Foster896C","Foster896D","Foster896E","Foster906A","Foster912A","Foster912B","Foster914A","Foster926A","Foster936A","Foster936B","Foster936C","Foster938A","Foster938B","Foster942A","Foster950A","Foster960A","Foster960B","Foster960C","Foster962A","Foster962B","Foster968A","Foster974A","Foster976A","Foster978A","Foster992A","Foster998A",{"Grassmann",{2,{6,3}}},{"Grid",{10,10,10}},{"Hamming",{4,6}},{"Hamming",{5,4}},{"Hamming",{6,3}},"HeuleGraph803","HeuleGraph826","HeuleGraph874",{"Hypercube",10},"IoninKharaghaniGraph","IvanovIvanovFaradjevGraph","JankoKharaghaniGraph936",{"Keller",5},{"Kneser",{12,5}},{"Kneser",{13,4}},{"Kneser",{13,5}},{"Kneser",{14,4}},{"Kneser",{14,5}},{"Kneser",{14,6}},{"Kneser",{15,4}},"LargeWittGraph",{"Mathon",0},{"Mathon",1},{"Mathon",2},{"MengerSponge",3},{"Mycielski",10},{"Mycielski",11},"NortonSmithGraph",{"Odd",7},"ShiKrotoveSoleGraph",{"SierpinskiCarpet",4},{"SierpinskiTetrahedron",6},"SuzukiGraph","TruncatedBinaryGolayCodeCosetDistance2Graph","TruncatedBinaryGolayCodeCosetGraph","U62ComplementGraph"};

data=Monitor[{g=#,TimeConstrained[GeodeticGraphQ[GraphData[#]],10]//Timing}&/@todo,g];//Timing

l=DeleteCases[data,{_,{_,$Aborted}}]

Cases[l,{_,{_,True}}]

Cases[data,{g_,{_,$Aborted}}:>g]

todo={{"SierpinskiCarpet",4}};

(data=Monitor[{g=#,TimeConstrained[GeodeticGraphQ[GraphData[#]],Infinity]//Timing}&/@todo,g])//Timing

Cases[data,{g_,{_,$Aborted}}:>g]

l=DeleteCases[data,{_,{_,$Aborted}}]

MissingFillin[l,"Geodetic","13.1"]

RenameGraphFiles[]