Distance-Hereditary Graph

Author

Eric W. Weisstein
December 10, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Distance-HereditaryGraph.nb.

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

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

Definition

https://arxiv.org/pdf/1608.01465.pdf

Classes

GraphClassesThatAreClass["DistanceHereditary"]

Intersection@@(GraphData[#,"Classes"]&/@GraphData["DistanceHereditary"])

Counts

https://oeis.org/A277862

1, 1, 2, 6, 18, 73, 308, 1484, 7492, 40010, 220676, 1253940, 7282316, 43096792, 259019070, 1577653196, 9720170360, 60492629435, 379820431422, 2403679290621, 15319255038074, 98255642978084, 633833391637128, 4110221883283079, 26781322507739916, 175268504233782739

Table[Count[ConnectedGraphs[n],_?(DistanceHereditaryGraphQ[#,Method->"SubgraphDistances"]&)],{n,7}]//Timing

Table[Count[ConnectedGraphs[n],_?(DistanceHereditaryGraphQ[#,Method->"EqualDistanceSums"]&)],{n,9}]//Timing

Table[Count[ConnectedGraphs[n],_?DistanceHereditaryGraphQ],{n,9}]//Timing

Table[Count[GraphData/@GraphData["Connected",n],_?DistanceHereditaryGraphQ],{n,9}]//Timing

Length/@Table[GraphData["DistanceHereditary",n],{n,7}]

Figure

GraphicsGrid[Flatten[Partition[#,UpTo[5]]&/@Map[Show[GraphData[#]//StyleGraphs,PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[Opacity[1],Black,Italic,14,FontFamily->"Times"]],PageWidth->500/5,TextAlignment->Center]]&,
Table[GraphData[{"Connected","DistanceHereditary"},n],{n,5}],{2}],1],ImageSize->700,Dividers->{{Thick,{True},Thick},{Thick,Thick,Thick,Thick,True,Thick,{True},Thick}}]

Algorithms

Table[Count[ConnectedGraphs[n],_?(DistanceHereditaryGraphQ[#,Method->"SubgraphDistances"]&)],{n,7}]//Timing

Counts:

Table[Count[ConnectedGraphs[n],_?(DistanceHereditaryGraphQ[#,Method->"EqualDistanceSums"]&)],{n,9}]//Timing

Any two equal:

Table[Count[ConnectedGraphs[n],_?DistanceHereditaryGraphQ],{n,9}]//Timing

Check

http://www.jaist.ac.jp/~uehara/graphs/#dist-here

dh5u=Graph[Range[0,4],UndirectedEdge@@@#]&/@Partition[SplitBy[ToExpression[StringSplit[Import["http://www.jaist.ac.jp/~uehara/graphs/distance_hereditary_graph/distance_hereditary_5.out","Lines"]]],#[[1]]==5&],2][[All,2]]

dh5e=Select[ConnectedGraphs[5],DistanceHereditaryGraphQ]

Sort[RecognizeGraph/@dh5u]===Sort[RecognizeGraph/@dh5e]

Parametrized families

<<MathWorld`Graphs`

Alkane

Table[GraphData[{"Alkane",n},"DistanceHereditary"],{n,10}]

AlternatingGroupGraph

Table[GraphData[{"AlternatingGroupGraph",n},"DistanceHereditary"],{n,2,6}]

Do[Print[{GraphData[{"AlternatingGroupGraph",n},"#"],DistanceHereditaryGraphQ@GraphData[{"AlternatingGroupGraph",n}]//Timing}],{n,2,6}]

Andrasfai

Table[GraphData[{"Andrasfai",n},"DistanceHereditary"],{n,10}]

Do[Print[{GraphData[{"Andrasfai",n},"#"],DistanceHereditaryGraphQ@GraphData[{"Andrasfai",n}]//Timing}],{n,10}]

Antelope m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Antelope"],
Piecewise[{{True,m==n==1}},False],
GraphData[#,"DistanceHereditary"]}&/@GraphData["Antelope"],{_,x_,x_}]

Antelope n×n

Table[GraphData[{"Antelope",{n,n}},"DistanceHereditary"],{n,15}]

Antiprism

Entity["Graph",{"Antiprism",n}]["DistanceHereditary"]

Table[GraphData[{"Antiprism",n},"DistanceHereditary"],{n,3,25}]

Do[Print[{GraphData[{"Antiprism",n},"#"],DistanceHereditaryGraphQ@GraphData[{"Antiprism",n}]//Timing}],{n,3,25}]

Apollonian

Table[GraphData[{"Apollonian",n},"DistanceHereditary"],{n,5}]

Do[Print[{GraphData[{"Apollonian",n},"#"],DistanceHereditaryGraphQ@GraphData[{"Apollonian",n}]//Timing}],{n,5}]

Barbell

Table[GraphData[{"Barbell",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{GraphData[{"Barbell",n},"#"],DistanceHereditaryGraphQ@GraphData[{"Barbell",n}]//Timing}],{n,3,20}]

BlackBishop m×n

Sort@DeleteCases[{
{m,n}=GraphData[#,"NotationRules","BlackBishop"],
Piecewise[{{True,m==n==1||m==n==3||Min[m,n]==2}},False],
GraphData[#,"DistanceHereditary"]}&/@GraphData["BlackBishop"],{_,x_,x_}]

BlackBishop n×n

Table[GraphData[{"BlackBishop",{n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"BlackBishop",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

Bishop m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Bishop"],
Piecewise[{{True,m==n==1}},False],
GraphData[#,"DistanceHereditary"]}&/@GraphData["Bishop"],{_,x_,x_}]

Bishop n×n

Table[GraphData[{"Bishop",{n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"Bishop",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

Book

Table[GraphData[{"Book",n},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"Book",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]

Bruhat

Table[GraphData[{"Bruhat",n},"DistanceHereditary"],{n,6}]

Do[Print[{gn=GraphData[{"Bruhat",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,6}]

Camel m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Camel"],
Piecewise[{{True,m==n==1}},False],
GraphData[#,"DistanceHereditary"]}&/@GraphData["Camel"],{_,x_,x_}]

Camel n×n

Table[GraphData[{"Camel",{n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"Camel",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

Centipede

Table[GraphData[{"Centipede",n},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"Centipede",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

CocktailParty

Table[GraphData[{"CocktailParty",n},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"CocktailParty",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

Complete

Entity["Graph",{"Complete",n}]["DistanceHereditary"]

Table[GraphData[{"Complete",n},"DistanceHereditary"],{n,30}]

Do[Print[{gn=GraphData[{"Complete",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["DistanceHereditary"]

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","CompleteBipartite"],
True,
GraphData[#,"DistanceHereditary"]}&/@GraphData["CompleteBipartite"],{_,x_,x_}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["DistanceHereditary"]

Table[GraphData[{"CompleteBipartite",{n,n}},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"CompleteBipartite",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["DistanceHereditary"]

Flatten[Table[GraphData[{"CompleteTripartite",{k,m,n}},"DistanceHereditary"],{n,10},{m,n},{k,m}],2]//Union

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["DistanceHereditary"]

Table[GraphData[{"CompleteTripartite",{n,n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"CompleteTripartite",{n,n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

CrossedPrism

Table[GraphData[{"CrossedPrism",2n},"DistanceHereditary"],{n,2,10}]

Do[Print[{gn=GraphData[{"CrossedPrism",2n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,2,10}]

Crown

Table[GraphData[{"Crown",n},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"Crown",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["DistanceHereditary"]

Table[GraphData[{"CubeConnectedCycle",n},"DistanceHereditary"],{n,3,8}]

Do[Print[{gn=GraphData[{"CubeConnectedCycle",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["DistanceHereditary"]

Table[GraphData[{"Cycle",n},"DistanceHereditary"],{n,3,30}]

Do[Print[{gn=GraphData[{"Cycle",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,30}]

CycleComplement

Table[GraphData[{"CycleComplement",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{gn=GraphData[{"CycleComplement",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,20}]

DiagonalIntersection

Table[GraphData[{"DiagonalIntersection",n},"DistanceHereditary"],{n,3,14}]

Do[Print[{gn=GraphData[{"DiagonalIntersection",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,14}]

Dipyramid

Table[GraphData[{"Dipyramid",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{gn=GraphData[{"Dipyramid",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,20}]

DorogovtsevGoltsevMendes

Inferred for n > 5:

Table[GraphData[{"DorogovtsevGoltsevMendes",n},"DistanceHereditary"],{n,7}]

Empty

Entity["Graph",{"Empty",n}]["DistanceHereditary"]

Table[GraphData[{"Empty",n},"DistanceHereditary"],{n,30}]

Do[Print[{gn=GraphData[{"Empty",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,30}]

FibonacciCube

Table[GraphData[{"FibonacciCube",n},"DistanceHereditary"],{n,15}]

Do[Print[{gn=GraphData[{"FibonacciCube",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,15}]

Flower

Table[GraphData[{"Flower",n},"DistanceHereditary"],{n,5,20}]

Do[Print[{gn=GraphData[{"Flower",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,5,20}]

FoldedCube

Table[GraphData[{"FoldedCube",n},"DistanceHereditary"],{n,2,10}]

Do[Print[{gn=GraphData[{"FoldedCube",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,2,10}]

Gear

Table[GraphData[{"Gear",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{gn=GraphData[{"Gear",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Giraffe m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Giraffe"],
Piecewise[{{True,m==n==1}},False],
GraphData[#,"DistanceHereditary"]}&/@GraphData["Giraffe"],{_,x_,x_}]

Giraffe n×n

Table[GraphData[{"Giraffe",{n,n}},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"Giraffe",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]

Goldberg

Table[GraphData[{"Goldberg",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{gn=GraphData[{"Goldberg",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["DistanceHereditary"]

Sort@DeleteCases[
Flatten[Table[{
{m,n},
Piecewise[{{True,Min[m,n]==1||m==n==2}},False],
GraphData[{"Grid",{m,n}},"DistanceHereditary"]},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["DistanceHereditary"]

Table[GraphData[{"Grid",{n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"Grid",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["DistanceHereditary"]

Sort@DeleteCases[
Flatten[Table[{
{k,m,n},
Piecewise[{{True,Max[k,m,n]==k m n||(Min[k,m,n]==1&&Max[k,m,n]==2)}},False],
GraphData[{"Grid",{k,m,n}},"DistanceHereditary"]},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["DistanceHereditary"]

Table[GraphData[{"Grid",{n,n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"Grid",{n,n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

HalvedCube

Table[GraphData[{"HalvedCube",n},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"HalvedCube",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

Hanoi

Table[GraphData[{"Hanoi",n},"DistanceHereditary"],{n,5}]

Do[Print[{gn=GraphData[{"Hanoi",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,5}]

Helm

Table[GraphData[{"Helm",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{gn=GraphData[{"Helm",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["DistanceHereditary"]

Table[GraphData[{"Hypercube",n},"DistanceHereditary"],{n,0,10}]

Do[Print[{gn=GraphData[{"Hypercube",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["DistanceHereditary"]

Table[GraphData[{"Keller",n},"DistanceHereditary"],{n,5}]

Do[Print[{gn=GraphData[{"Keller",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,5}]

King m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","King"],
XXX,
GraphData[#,"DistanceHereditary"]}&/@GraphData["King"],{_,x_,x_}]

King n×n

Table[GraphData[{"King",{n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"King",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["DistanceHereditary"]

Sort@DeleteCases[
Flatten[Table[{
{m,n},
Piecewise[{{True,m==n==1}},False],
GraphData[{"Knight",{m,n}},"DistanceHereditary"]},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["DistanceHereditary"]

Table[GraphData[{"Knight",{n,n}},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"Knight",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["DistanceHereditary"]

Table[GraphData[{"Ladder",n},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"Ladder",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]

LadderRung

Table[GraphData[{"LadderRung",n},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"LadderRung",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]

MengerSponge

Table[GraphData[{"MengerSponge",n},"DistanceHereditary"],{n,3}]

Do[Print[{gn=GraphData[{"MengerSponge",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["DistanceHereditary"]

Table[GraphData[{"MoebiusLadder",n},"DistanceHereditary"],{n,3,25}]

Do[Print[{gn=GraphData[{"MoebiusLadder",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["DistanceHereditary"]

Table[GraphData[{"Mycielski",n},"DistanceHereditary"],{n,11}]

Do[Print[{gn=GraphData[{"Mycielski",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["DistanceHereditary"]

Table[GraphData[{"Odd",n},"DistanceHereditary"],{n,7}]

Do[Print[{gn=GraphData[{"Odd",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,7}]

Pan

Table[GraphData[{"Pan",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{gn=GraphData[{"Pan",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["DistanceHereditary"]

Table[GraphData[{"Path",n},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"Path",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]

PathComplement

Table[GraphData[{"PathComplement",n},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"PathComplement",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["DistanceHereditary"]

Table[GraphData[{"Prism",n},"DistanceHereditary"],{n,3,25}]

Do[Print[{gn=GraphData[{"Prism",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,25}]

Queen m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Queen"],
Piecewise[{{True,Min[m,n]==1||(m==2&&n==3)}},False],
GraphData[#,"DistanceHereditary"]}&/@GraphData["Queen"],{_,x_,x_}]

Queen n×n

Table[GraphData[{"Queen",{n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"Queen",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

Rook m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Rook"],
Piecewise[{{True,Min[m,n]==1||m==n==2}},False],
GraphData[#,"DistanceHereditary"]}&/@GraphData["Rook"],{_,x_,x_}]

Rook n×n

Table[GraphData[{"Rook",{n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"Rook",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

RookComplement m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","RookComplement"],
Piecewise[{{True,m==n==1}},False],
GraphData[#,"DistanceHereditary"]}&/@GraphData["RookComplement"],{_,x_,x_}]

RookComplement n×n

Table[GraphData[{"RookComplement",{n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"RookComplement",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

SierpinskiCarpet

Table[GraphData[{"SierpinskiCarpet",n},"DistanceHereditary"],{n,4}]

Do[Print[{gn=GraphData[{"SierpinskiCarpet",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,4}]

SierpinskiGasket

Table[GraphData[{"SierpinskiGasket",n},"DistanceHereditary"],{n,5}]

Do[Print[{gn=GraphData[{"SierpinskiGasket",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,5}]

SierpinskiTetrahedron

Table[GraphData[{"SierpinskiTetrahedron",n},"DistanceHereditary"],{n,6}]

Do[Print[{gn=GraphData[{"SierpinskiTetrahedron",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,4}]

StackedBook m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","StackedBook"],
XXX,
GraphData[#,"DistanceHereditary"]}&/@GraphData["StackedBook"],{_,x_,x_}]

StackedBook n×n

Table[GraphData[{"StackedBook",{n,n}},"DistanceHereditary"],{n,10}]

Do[Print[{gn=GraphData[{"StackedBook",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,10}]

StackedPrism m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","StackedPrism"],
XXX,
GraphData[#,"DistanceHereditary"]}&/@GraphData["StackedPrism"],{_,x_,x_}]

StackedPrism n×n

Table[GraphData[{"StackedPrism",{n,n}},"DistanceHereditary"],{n,3,5}]

Do[Print[{gn=GraphData[{"StackedPrism",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["DistanceHereditary"]

Table[GraphData[{"Star",n},"DistanceHereditary"],{n,25}]

Do[Print[{gn=GraphData[{"Star",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,25}]

Sun

Table[GraphData[{"Sun",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{gn=GraphData[{"Sun",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Sunlet

Table[GraphData[{"Sunlet",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{gn=GraphData[{"Sunlet",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,20}]

TorusGrid m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","TorusGrid"],
False,
GraphData[#,"DistanceHereditary"]}&/@GraphData["TorusGrid"],{_,x_,x_}]

TorusGrid n×n

Table[GraphData[{"TorusGrid",{n,n}},"DistanceHereditary"],{n,3,10}]

Do[Print[{gn=GraphData[{"TorusGrid",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,10}]

Transposition

Entity["Graph",{"Transposition",n}]["DistanceHereditary"]

Table[GraphData[{"Transposition",n},"DistanceHereditary"],{n,6}]

Do[Print[{gn=GraphData[{"Transposition",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,6}]

Triangular

Table[GraphData[{"Triangular",n},"DistanceHereditary"],{n,2,10}]

Do[Print[{gn=GraphData[{"Triangular",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,2,10}]

TriangularGrid

Table[GraphData[{"TriangularGrid",n},"DistanceHereditary"],{n,0,10}]

Do[Print[{gn=GraphData[{"TriangularGrid",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,0,10}]

TriangularHoneycombAcuteKnight

Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"DistanceHereditary"],{n,20}]

TriangularHoneycombBishop

Table[GraphData[{"TriangularHoneycombBishop",n},"DistanceHereditary"],{n,9}]

TriangularHoneycombObtuseKnight

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"DistanceHereditary"],{n,20}]

TriangularHoneycombQueen

Table[GraphData[{"TriangularHoneycombQueen",n},"DistanceHereditary"],{n,10}]

TriangularHoneycombRook

Table[GraphData[{"TriangularHoneycombRook",n},"DistanceHereditary"],{n,10}]

TriangularSnake

Table[GraphData[{"TriangularSnake",n},"DistanceHereditary"],{n,1,20,2}]

Do[Print[{gn=GraphData[{"TriangularSnake",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,1,20,2}]

Web

Table[GraphData[{"Web",n},"DistanceHereditary"],{n,3,20}]

Do[Print[{gn=GraphData[{"Web",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["DistanceHereditary"]

Table[GraphData[{"Wheel",n},"DistanceHereditary"],{n,4,20}]

Do[Print[{gn=GraphData[{"Wheel",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,4,20}]

WheelComplement

Table[GraphData[{"WheelComplement",n},"DistanceHereditary"],{n,4,20}]

Do[Print[{gn=GraphData[{"WheelComplement",n},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,4,20}]

WhiteBishop n×n

Table[GraphData[{"WhiteBishop",{n,n}},"DistanceHereditary"],{n,2,10}]

Do[Print[{gn=GraphData[{"WhiteBishop",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,2,10}]

Zebra m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Zebra"],
Piecewise[{{True,m==n==1}},False],
GraphData[#,"DistanceHereditary"]}&/@GraphData["Zebra"],{_,x_,x_}]

Zebra n×n

Table[GraphData[{"Zebra",{n,n}},"DistanceHereditary"],{n,20}]

Do[Print[{gn=GraphData[{"Zebra",{n,n}},"#"],DistanceHereditaryGraphQ@GraphData[gn]//Timing}],{n,20}]