Harary Graph

Author

Eric W. Weisstein
August 2, 2023

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

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

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

Figures

Old Combinatorica V4

<<DiscreteMath`Combinatorica`

Off[General::"stop"]

?Harary

Show[GraphicsArray[Table[Graphics[showGraph[RecognizeGraph[Harary[k,n]],PointSize[.1]]],{n,2,5},{k,n-1}]],GraphicsSpacing->{.1,-.4}]

Show[GraphicsArray[Table[Graphics[showGraph[RecognizeGraph[harary[k,n]],PlotStyles->{PointSize[.1]}]],{n,2,5},{k,n-1}],GraphicsSpacing->{.1,-.3}]]

Combinatorica V5

Show[GraphicsArray[Table[ShowGraph[Harary[k,n],DisplayFunction->Identity,VertexColor->Red,VertexStyle->Disc[Large]],{n,2,6},{k,2,n-1}]]]

V8 Built-in

GraphData["Harary*"]

GraphData["Harary"]

GraphData[{"Antiprism",4},"NotationRules"]

gs={#,RecognizeGraph[HararyGraph@@#]}&/@Flatten[Table[{k,n},{n,3,10},{k,2,n-1}],1];

Cases[gs,{_,{}}]

Cases[gs,{_,{_Integer,_Integer}}]

%[[All,1]]

gs={#,RecognizeGraph[HararyGraph@@#]}&/@Flatten[Table[{k,n},{n,3,50},{k,2,n-1}],1];//Timing

rules=Sort[(#[[2]]->{#[[1]]})&/@DeleteCases[gs,{_,{_Integer,_Integer}|{}}]]

Length[rules]

GraphicsGrid[Map[Show[GraphData[#,"Image"],PlotLabel->TextCell[Column[{Style[GraphData[#,"Name"],Italic],Subscript[Style["H",Italic],h="Harary"/.GraphData[#,"NotationRules"];Row[{h[[1]],",",h[[2]]}]]},Alignment->Center],TextAlignment->Center,PageWidth->125]]&,Table[{"Harary",{k,n}},{n,3,7},{k,2,n-1}],{2}],ImageSize->600]

Properties

Classes

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

XXX

harary[1, n_] := Path[n]
harary[k_, n_] := Harary[k, n]

Map[EdgeConnectivity,Table[harary[k,n],{n,2,5},{k,n-1}],{2}]

Map[M,Table[harary[k,n],{n,2,5},{k,n-1}],{2}]

Table[Ceiling[k n/2],{n,2,5},{k,n-1}]

Map[EdgeConnectivity,Table[Harary[k,n],{n,2,5},{k,n-1}],{2}]

Map[M,Table[Harary[k,n],{n,2,5},{k,n-1}],{2}]

Table[Ceiling[k n/2],{n,2,5},{k,n-1}]

FibonacciCube

Entity["Graph",{"Harary",{k,n}}]["FibonacciCube"]

GraphData[{"Harary","FibonacciCube"}]

LucasCube

Entity["Graph",{"Harary",{k,n}}]["LucasCube"]

GraphData[{"Harary","LucasCube"}]

Pell

Entity["Graph",{"Harary",{k,n}}]["Pell"]

GraphData[{"Harary","Pell"}]

Embeddings

h=GraphData["Harary*"]

GraphData/@h

GraphData[#,"AllImages"]&/@h

CircularHamiltonianEmbedding[g_System`Graph,h_List,off_:0]:=Module[{n=VertexCount[g]},SetProperty[g,VertexCoordinates->(Thread[Ordering[h]->(Through[{Cos,Sin}[If[Mod[n,2]==1,Pi/2,0]+2.π (#+off)/n]]&/@Range[0,n-1])])]]
GrabLines[g_System`Graph]:=Sort[Sort/@Chop[Cases[Normal[Graphics[GraphPlot[g]]],Line[l_]:>l,{0,∞}]]]
EmbeddingUnion[gs_]:=SplitBy[Sort[{GrabLines[#],#}&/@gs],First][[All,1,2]]
LeftRightUniqueGraphs[g_]:=EmbeddingUnion[Select[g,LeftRightSymmetricEmbeddingQ]]
LeftRightSymmetricEmbeddingQ[g_System`Graph]:=Module[{g1,g2},
g1=GrabLines[g];
g2=Sort[Sort/@(g1/.{{x1_,y1_},{x2_,y2_}}:>{{-x1,y1},{-x2,y2}})];
Union[Chop[g1-g2]]==={{{0,0},{0,0}}}
]

g1=With[{g={"Harary",{3,7}}},CircularHamiltonianEmbedding[GraphData[g],#]&/@GraphData[g,"UndirectedHamiltonianCycles"]]

g1nice=LeftRightUniqueGraphs[g1]

e1={{"Harary",{3,7}},{0,ToCommonEdges[#,GraphData[{"Harary",{3,7}}]]&/@g1nice//Chop}}

g2=With[{g={"Harary",{3,9}}},CircularHamiltonianEmbedding[GraphData[g],#]&/@GraphData[g,"UndirectedHamiltonianCycles"]]

g2nice=LeftRightUniqueGraphs[g2]

e2={{"Harary",{3,9}},{0,ToCommonEdges[#,GraphData[{"Harary",{3,9}}]]&/@g2nice//Chop}}

g3=With[{g={"Harary",{5,9}}},CircularHamiltonianEmbedding[GraphData[g],#]&/@FindHamiltonianCycle[GraphData[g],All][[All,All,1]]];

g3nice=LeftRightUniqueGraphs[g3]

Length[g3nice]

e3={{"Harary",{5,9}},{0,ToCommonEdges[#,GraphData[{"Harary",{5,9}}]]&/@g3nice//Chop}}

l={e1,e2,e3}

l2={#[[1]],{0,Prepend[Table[{"Circular"},{Length[#[[2,2]]]-1}],{"Circular","Primary"}]}}&/@l

GraphData

GraphDataString

Print[GraphDataString[
FromUnorderedPairs[List@@@System`EdgeList[HararyGraph@@#]],
"StandardName"->{"Harary",#},
"Name"->"("<>ToString[#[[1]]]<>","<>ToString[#[[2]]]<>")\[Hyphen]Harary graph",
"Vertices"->None,
"Information"->"HararyGraph",
"NotationRules"->{"Harary"->#},
"Classes"->{"Harary"},
"Notation"->Subscript["H",Row[{#[[1]],",",#[[2]]}]],
Debug->True,
TimeConstraint->60
]]&/@{{3,7},{3,9},{5,9}}