k-Cyclic Graph

Author

Eric W. Weisstein
January 20, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/k-CyclicGraph.nb.

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

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

Import

KCyclicEdgeLists[1]={};
KCyclicEdgeLists[2]={};
KCyclicEdgeLists[k_]:=Module[{dir="/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/FlowProblems/KCyclic/"},ToExpression["{"<>StringTake[Import[dir<>"C"<>ToString[k],"String"],{12,-5}]<>"}"]
]
KCyclicGraphs[k_]:=Graph[UndirectedEdge@@@#]&/@Reverse[KCyclicEdgeLists[k]]

Lengths

Table[Length[KCyclicEdgeLists[k]],{k,17}]//Timing

Figure

GraphicsGrid[
Flatten[Partition[#,6,6,{1,1},{}]&/@Map[Show[GraphData[#,"Image"],PlotLabel->TextCell[Style[StringReplace[GraphData[#,"Name"],"\[Hyphen]"->"-"],Italic,FontFamily->"Times"],PageWidth->500/6,TextAlignment->Center]]&,Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,7}],{2}],1],Dividers->All,ImageSize->500,Alignment->Top
]

By k

3

KCyclicGraphs[3]

4

c4=KCyclicGraphs[4]

RecognizeGraph/@c4

5

GraphicsGrid[Partition[c5=KCyclicGraphs[5],5,5,{1,1},{}]]

r5=RecognizeGraph/@c5

6

GraphicsGrid[Partition[c6=KCyclicGraphs[6],5,5,{1,1},{}]]

r6=RecognizeGraph/@c6

GraphicsGrid[Partition[GraphData/@r6,5,5,{1,1},{}]]

7

GraphicsGrid[Partition[c7=KCyclicGraphs[7],5,5,{1,1},{}]]

r7=RecognizeGraph/@c7

GraphicsGrid[Partition[GraphData/@r7,5,5,{1,1},{}]]

8+

Select[RecognizeGraph[#,"Cache"->"InternalOnly","StandardName"->False]&/@Select[KCyclicGraphs[8],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Select[RecognizeGraph[#,"Cache"->"InternalOnly","StandardName"->False]&/@Select[KCyclicGraphs[9],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Sort@Select[RecognizeGraph[#,"Cache"->"InternalOnly","StandardName"->False]&/@Select[KCyclicGraphs[10],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Tally[%[[All,1]]]

Select[RecognizeGraph[#,"Cache"->"CanonicalGraph"]&/@Select[KCyclicGraphs[11],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Tally[%[[All,1]]]

Select[RecognizeGraph[#,"Cache"->"CanonicalGraph"]&/@Select[KCyclicGraphs[12],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Tally[%[[All,1]]]

k-Cyclic

Counts of connected graphs

Number of connected graphs on n nodes: 1, 1, 1, 2, 6, 21, 112, 853, 11117,

A001349

8

all8=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,8}],1]]

Length[all8]

Count[all8,{}]

9

all9=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,9}],1]]

Length[all9]

Sort@Select[Tally[GraphData[#,"V"]&/@all9],FreeQ[#,GraphData]&]//Quiet

Count[all9,{}]

10

all10=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,10}],1]]

Length[all10]

Sort@Select[Tally[GraphData[#,"V"]&/@all10],FreeQ[#,GraphData]&]//Quiet

Count[all10,{}]

12

Length[all12=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,12}],1]]]//Timing

Sort@Select[Tally[GraphData[#,"V"]&/@all12],FreeQ[#,GraphData]&]//Quiet

13

Length[all13=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,13}],1]]]//Timing

Sort@Select[Tally[GraphData[#,"V"]&/@all13],FreeQ[#,GraphData]&]//Quiet

14

Length[all14=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,14}],1]]]//Timing

Sort@Select[Tally[GraphData[#,"V"]&/@all14],FreeQ[#,GraphData]&]//Quiet

15

Length[all15=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,15}],1]]]//Timing

Sort@Select[Tally[GraphData[#,"V"]&/@all15],FreeQ[#,GraphData]&]//Quiet

16

Length[all16=Union[Flatten[Table[RecognizeGraph[#,"Cache"->"CanonicalGraph","StandardName"->False]&/@KCyclicGraphs[n],{n,3,16}],1]]]//Timing

Sort@Tally[all16[[All,1]]]

17

Length[all17=Union[Flatten[Table[RecognizeGraph[#,"Cache"->"CanonicalGraph","StandardName"->False]&/@KCyclicGraphs[n],{n,17}],1]]]//Timing

Sort@Tally[all17[[All,1]]]

con6=Sort[Cases[GraphData[#,"StandardNames"],{6,_}][[1]]&/@GraphData["Connected",6]]

Complement[con6,Cases[all17,{6,_}]]

GraphData[{6,156},"#"]

GraphData

<<MathWorld`Graphs`

Existing

Length/@(gs=Table[KCyclicGraphs[n],{n,17}])//Timing

data=Sort@DeleteCases[Flatten[MapIndexed[{RecognizeGraph[#,"Cache"->"InternalOnly"],{"KCyclic",#2}}&,gs,{2}],1],{{},_}];//Timing

Length[data]

AlternateStandardNames

Length[l={#[[1,1]],{0,SortBy[Union[DeleteCases[GraphData[#[[1,1]],"AlternateStandardNames"],{"KCyclic",_}],Complement[#[[All,2]],{#[[1,1]]}]],Function[f,First[Flatten[{f}]]]]}}&/@SplitBy[data,First]]

l2=Select[l,#[[2,2]]=!=GraphData[#[[1]],"AlternateStandardNames"]&]

PropertyReplace[l2,"AlternateStandardNames",Select[$Subdirs,ToExpression[#]>=13.3&]]

RenameGraphFiles[]

KCyclicIndices

l={#[[1,1]],{0,#[[All,2]][[All,2]]}}&/@SplitBy[data,First];

GraphData[{"KCyclic",{9,56}},"KCyclicIndices"]

l2=Select[l,#[[2,2]]=!=GraphData[#[[1]],"KCyclicIndices"]&]

PropertyReplace[l2,"KCyclicIndices",Select[$Subdirs,ToExpression[#]>=13.3&]]

RenameGraphFiles[]

Add up to (Subscript[C, 10])-cyclic

Length[gs=Table[KCyclicGraphs[n],{n,10}]]

Cases[Flatten[MapIndexed[{#,RecognizeGraph[#,"Cache"->"InternalOnly"],{"KCyclic",#2}}&,gs,{2}],1],{_,{},_}]

Add up to (Subscript[C, 11])-cyclic

Length[gs=Table[KCyclicGraphs[n],{n,11}]]

new=SortBy[{#[[1,1]],#[[All,-1]]}&/@SplitBy[SortBy[Cases[Flatten[MapIndexed[{CanonicalGraph@#,RecognizeGraph[#,"Cache"->"InternalOnly"],{"KCyclic",#2}}&,gs,{2}],1],{_,{},_}],First],First],#[[2,1]]&]

Put[new,"~/graphs.m"]

Tally[VertexCount/@new[[All,1]]]//Sort

Add

Length[new=Get["~/graphs.m"]]

RecognizeGraph[LineGraph[new[[43,1]]]]//Timing

file=OpenAppend["~/kcyclic.m"]

p=FirstPosition[new[[All,2]],{"KCyclic",{11,252}},{0}][[1]]

WriteString[file,GraphDataString[#,
"StandardName"->First[#2],
"AlternateStandardNames"->Rest[#2],
"Name"->ToString[#2[[1,2,1]]]<>"\[Hyphen]cyclic graph "<>ToString[#2[[1,2,2]]],
"KCyclicIndices"->#2[[All,2]],
Debug->True,
TimeConstraint->60,
"Skip"->{"DistinguishingNumber"}
]]&@@@Drop[new,p]

Close[file]