Cyclic Edge Connectivity

Author

Eric W. Weisstein
December 9, 2023

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

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

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

Example

CyclicEdgeConnectivity[PetersenGraph[]]

HighlightGraph[GraphData["PetersenGraph"],UndirectedEdge@@@Table[{i,i+5},{i,5}],GraphHighlightStyle->"Dashed",ImageSize->250]

Table

GraphDataCountTable["CyclicEdgeConnectivity",Flatten[{
(* misc *)
"Andrasfai"->008586,"CocktailParty"->008588,"Complete"->008585,"Dipyramid"->000027,"Prism"->255176,"Sun"->005843,"Web"->255176,

(* 0 *) Thread[{"Alkane","Bishop","Book","Camel","Centipede","Cycle","Empty","Gear","Helm","LadderRung","Pan","Path","Star","Sunlet","TriangularHoneycombAcuteKnight","TriangularHoneycombRook","Wheel"}->000007],
Thread[{"DoubleCone","Trapezohedron"}->27], (* 1, 2, 3, ... *)
(* 1 *) Thread[{"Barbell"}->000012],
(* 2 *) Thread[{"Hanoi","Ladder","TriangularSnake"}->007395],
(* 4 *) Thread[{"CrossedPrism",{"Grid",2},"MoebiusLadder","SierpinskiCarpet","SierpinskiSieve","TriangularGrid"}->010709],
(* 6 *) Thread[{"Antiprism","Flower"}->010722],
(* 8 *) (* {"Grid", 3} *)
(* 9 *)Thread[{"SierpinskiTetrahedron"}->010734]
}]]

Parametrized families

<<MathWorld`Graphs`

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"CyclicEdgeConnectivity"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"CyclicEdgeConnectivity"],{n,20}]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Simplify[SeriesCoefficient[gf,{x,0,n}],n>1]

HighlightGraph[GraphData[{"Andrasfai",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{{3,4},{7,8},{1,2},{5,6}}},
{4,1,{}},
{5,1,{}}}

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"CyclicEdgeConnectivity"],{n,20}]

Antiprism

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

seq=Table[GraphData[{"Antiprism",n},"CyclicEdgeConnectivity"],{n,3,25}]

HighlightGraph[GraphData[{"Antiprism",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{{1,4},{1,5},{2,4},{2,6},{3,5},{3,6}}},
{4,1,{{1,4},{1,2},{2,5},{5,6},{4,8},{7,8}}},
{5,1,{{1,5},{1,10},{4,5},{4,9},{6,10},{8,9}}}}

Apollonian

seq=Table[GraphData[{"Apollonian",n},"CyclicEdgeConnectivity"],{n,5}]

FindSequenceFunction[seq,n]

Barbell

seq=Table[GraphData[{"Barbell",n},"CyclicEdgeConnectivity"],{n,3,20}]

HighlightGraph[GraphData[{"Barbell",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{{1,6}}},
{4,1,{{4,8}}},
{5,1,{{5,10}}}}

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"CyclicEdgeConnectivity"],{n,20}]

FullSimplify[FindSequenceFunction[Rest@seq,n-1],n∈Integers]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"CyclicEdgeConnectivity"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"CyclicEdgeConnectivity"],{n,20}]

Annotate[#,ImageSize->Tiny]&/@Table[GraphData[{"Book",n}],{n,6}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"CyclicEdgeConnectivity"],{n,6}]

FindSequenceFunction[seq,n]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"CyclicEdgeConnectivity"],{n,20}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"CyclicEdgeConnectivity"],{n,20}]

Table[6(n-2)<=3(2n-3),{n,3,6}]

HighlightGraph[GraphData[{"CocktailParty",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{{2,6},{3,6},{2,4},{1,4},{1,5},{3,5}}},
{4,2,Select[GraphData[{"CocktailParty",4},"Edges","List"],Length[Intersection[#,{1,2,3}]]==1&]},
{5,2,Select[GraphData[{"CocktailParty",5},"Edges","List"],Length[Intersection[#,{3,8,10}]]==1&]},
{6,2,Select[GraphData[{"CocktailParty",6},"Edges","List"],Length[Intersection[#,{5,8,10}]]==1&]},
{6,2,Select[GraphData[{"CocktailParty",6},"Edges","List"],Length[Intersection[#,{3,5,10}]]==1&]}
}

Complete

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

seq=Table[GraphData[{"Complete",n},"CyclicEdgeConnectivity"],{n,30}]

FindSequenceFunction[seq,n]

CompleteBipartite m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"CyclicEdgeConnectivity"]
},{n,10},{m,n}],1],
{{1|2|3,_},0}]

CompleteBipartite n×n

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

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CyclicEdgeConnectivity"],{n,20}]

FindSequenceFunction[seq,n]//FullSimplify

CompleteTripartite k×m×n

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

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"CyclicEdgeConnectivity"]
},{n,10},{m,n},{k,m}],2],
{{1,1|2,_},0}]

CompleteTripartite n×n×n

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

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"CyclicEdgeConnectivity"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"CyclicEdgeConnectivity"],{n,2,12}]

HighlightGraph[GraphData[{"CrossedPrism",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{{4,1,{{1,2},{3,4},{5,6},{7,8}}},{6,9,{{6,7},{5,12},{4,9},{2,3}}},{8,4,{{11,12},{13,14},{5,6},{3,4}}}}

With[{g=GraphData[{"CrossedPrism",8}]},SelectFirst[Subsets[EdgeList[g],{4}],Length[cc=ConnectedGraphComponents[EdgeDelete[g,#]]]===2&&NoneTrue[cc,AcyclicGraphQ]&]]

EdgeDelete[GraphData[{"CrossedPrism",8}],{1\[UndirectedEdge]2,3\[UndirectedEdge]4,9\[UndirectedEdge]10,11\[UndirectedEdge]12}]

GraphData[{"CrossedPrism",8},"Graphics"]

v={{0,0},{7,0},Sequence@@Table[{i,1},{i,0,7}],{3,2},{4,2},{0,3},{3,3},{4,3},{7,3}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,10,16,15,14,13,3,1,7],{2,6},e[3,4,5,6,7,8,9,10],e[14,11,12,15],{13,5},{4,12},{9,11},{8,16}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Crown

seq=Table[GraphData[{"Crown",n},"CyclicEdgeConnectivity"],{n,3,20}]

HighlightGraph[GraphData[{"Crown",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{}},
{4,1,{{1,2},{5,6},{3,4},{7,8}}},
{5,2,{{2,9},{1,9},{3,10},{4,7},{5,8},{5,6},{3,6},{1,7}}}}

Cycle

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

seq=Table[GraphData[{"Cycle",n},"CyclicEdgeConnectivity"],{n,3,20}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"CyclicEdgeConnectivity"],{n,3,20}]

Crown

seq=Table[GraphData[{"Crown",n},"CyclicEdgeConnectivity"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"CyclicEdgeConnectivity"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"CyclicEdgeConnectivity"],{n,3,20}]

HighlightGraph[GraphData[{"Dipyramid",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{4,1,{{1,4},{1,5},{2,4},{2,6},{3,5},{3,6}}},
{5,1,{{1,4},{1,6},{2,5},{2,7},{4,7},{5,7},{3,5},{3,6}}},
{6,1,{{1,4},{1,7},{5,7},{3,5},{2,8},{4,8},{6,8},{3,8}}}}

DutchWindmill

DeleteCases[{#,GraphData[#,"NotationRules","DutchWindmill"],GraphData[#,"CyclicEdgeConnectivity"]}&/@GraphData["DutchWindmill"],{_,_,0}]

GraphicsGrid[Partition[GraphData/@GraphData["DutchWindmill",;;20],UpTo[5]]]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"CyclicEdgeConnectivity"],{n,15}]

FindSequenceFunction[seq,n]//Head//Timing

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

Flower

seq=Table[GraphData[{"Flower",n},"CyclicEdgeConnectivity"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"CyclicEdgeConnectivity"],{n,2,10}]

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

Gear

seq=Table[GraphData[{"Gear",n},"CyclicEdgeConnectivity"],{n,3,20}]

HighlightGraph[GraphData[{"Gear",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{}},
{4,1,{}},
{5,1,{}},
{6,1,{}}}

FindSequenceFunction[seq,n]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"CyclicEdgeConnectivity"],{n,20}]

Goldberg

seq=Table[GraphData[{"FoldedCube",n},"CyclicEdgeConnectivity"],{n,2,10}]

Grid m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"CyclicEdgeConnectivity"],
Piecewise[{{0,Min[m,n]==1||m==n==2||m n==6||m==n==3},{2,Min[m,n]==2},{3,Min[m,n]==3}},4]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

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

seq=Table[GraphData[{"Grid",{n,n}},"CyclicEdgeConnectivity"],{n,20}]

HighlightGraph[GraphData[{"Grid",{#,#}},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{4,1,{{5,9},{6,10},{6,7},{2,3}}},
{5,1,{{2,3},{7,8},{6,11},{7,12}}},
{6,1,{{2,3},{8,9},{7,13},{8,14}}}}

Grid k×m×n

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

Grid n×n×n

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

seq=Table[GraphData[{"Grid",{n,n,n}},"CyclicEdgeConnectivity"],{n,10}]

GraphData[{"Grid",{3,3,3}},"Graph","Labeled"]

cut={{13,22},{14,23},{16,25},{17,26},{19,22},{20,23},{23,24},{26,27}};

HighlightGraph[GraphData[{"Grid",{3,3,3}}],UndirectedEdge@@@cut,GraphHighlightStyle->"Dotted"]

EdgeDelete[GraphData[{"Grid",{3,3,3}}],UndirectedEdge@@@cut]

ConnectedGraphComponents@%

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"CyclicEdgeConnectivity"],{n,10}]

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]

SeriesCoefficient[gf,{x,0,n}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"CyclicEdgeConnectivity"],{n,5}]

HighlightGraph[GraphData[{"Hanoi",#},"Graph",{"All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{2,1,{{7,8},{3,5}}},
{3,1,{{2,4},{3,5}}},
{4,1,{{2,4},{3,5}}}}

Helm

seq=Table[GraphData[{"Helm",n},"CyclicEdgeConnectivity"],{n,3,20}]

HighlightGraph[GraphData[{"Helm",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{}},
{4,1,{}},
{5,1,{}},
{6,1,{}}}

Hypercube

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

seq=Table[GraphData[{"Hypercube",n},"CyclicEdgeConnectivity"],{n,0,10}]

FindSequenceFunction[seq,n+1]

Jahangir

DeleteCases[GraphData[#,{"#","CyclicEdgeConnectivity"}]&/@GraphData["Jahangir"],{_,0}]

GraphicsGrid[Partition[GraphData/@GraphData["Jahangir",;;10],UpTo[5]]]

Keller

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

seq=Table[GraphData[{"Keller",n},"CyclicEdgeConnectivity"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"CyclicEdgeConnectivity"],{n,10}]

FindSequenceFunction[seq,n]//Factor

Knight m×n

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

Knight n×n

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

seq=Table[GraphData[{"Knight",{n,n}},"CyclicEdgeConnectivity"],{n,20}]

Ladder

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

seq=Table[GraphData[{"Ladder",n},"CyclicEdgeConnectivity"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"CyclicEdgeConnectivity"],{n,20}]

Lollipop

GraphData[{"Lollipop",{6,4}}]

DeleteCases[{#,With[{n=GraphData[#,"NotationRules","Lollipop"][[1]]},Piecewise[{{0,n<6}},3(n-3)]],GraphData[#,"CyclicEdgeConnectivity"]}&/@GraphData["Lollipop"],{_,x_,x_}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"CyclicEdgeConnectivity"],{n,3}]

Table[GraphData[{"MengerSponge",n}],{n,2}]

Table[GraphData[{"MengerSponge",n},"Graph","3D"],{n,2}]

MoebiusLadder

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

seq=Table[GraphData[{"MoebiusLadder",n},"CyclicEdgeConnectivity"],{n,3,25}]

HighlightGraph[GraphData[{"MoebiusLadder",#},"Graph",{"All","Labeled"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{4,1,{{3,4},{7,8},{1,2},{5,6}}},
{5,1,{{6,7},{1,2},{3,4},{8,9}}},
{6,1,{{10,11},{4,5},{2,3},{8,9}}}}

Mycielski

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

seq=Table[GraphData[{"Mycielski",n},"CyclicEdgeConnectivity"],{n,11}]

FullSimplify[FindSequenceFunction[Rest@seq,n-1],n∈Integers]

Odd

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

seq=Table[GraphData[{"Odd",n},"CyclicEdgeConnectivity"],{n,7}]

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

Path

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

seq=Table[GraphData[{"Path",n},"CyclicEdgeConnectivity"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"CyclicEdgeConnectivity"],{n,20}]

Table[Piecewise[{{0,n<6},{4,n==6}},3(n-5)],{n,20}]

Prism

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

seq=Table[GraphData[{"Prism",n},"CyclicEdgeConnectivity"],{n,3,25}]

HighlightGraph[GraphData[{"Prism",#},"Graph",{"All","Labeled"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{{1,4},{2,5},{3,6}}},
{4,1,{{3,4},{7,8},{1,2},{5,6}}},
{5,1,{{1,5},{6,10},{2,3},{7,8}}}}

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"CyclicEdgeConnectivity"],{n,10}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]//Factor

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"CyclicEdgeConnectivity"],{n,10}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]//Factor

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"CyclicEdgeConnectivity"],{n,10}]

FindSequenceFunction[Drop[seq,2],n-2]//Factor

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"CyclicEdgeConnectivity"],{n,4}]

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

{
HighlightGraph[GraphData[{"SierpinskiCarpet",2}],UndirectedEdge@@@{{14,23},{24,22},{30,29},{28,33}},GraphHighlightStyle->"Dashed"],
HighlightGraph[GraphData[{"SierpinskiCarpet",3}],UndirectedEdge@@@{{44,71},{70,72},{89,90},{88,101}},GraphHighlightStyle->"Dashed"]
}

SierpinskiSieve

seq=Table[GraphData[{"SierpinskiSieve",n},"CyclicEdgeConnectivity"],{n,5}]

HighlightGraph[GraphData[{"SierpinskiSieve",#},"Graph",{"All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{{3,7},{3,5},{2,5},{2,4}}},
{4,1,{{3,7},{3,5},{2,5},{2,4}}},
{5,1,{{3,7},{3,5},{2,5},{2,4}}}}

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"CyclicEdgeConnectivity"],{n,6}]

Table[GraphData[{"SierpinskiTetrahedron",n}],{n,3}]

Table[GraphData[{"SierpinskiTetrahedron",n},"Graph",{"Labeled","3D"}],{n,2}]

Select[EdgeList[g],FreeQ[#,1]&&Length[Intersection[List@@#,{2,3,4}]]==1&]

Length[%]

HighlightGraph[g=GraphData[{"SierpinskiTetrahedron",2},"Graph","3D"],Select[EdgeList[g],FreeQ[#,1]&&Length[Intersection[List@@#,{2,3,4}]]==1&],GraphHighlightStyle->"Dashed"]

HighlightGraph[g=GraphData[{"SierpinskiTetrahedron",2},"Graph"],Select[EdgeList[g],FreeQ[#,1]&&Length[Intersection[List@@#,{2,3,4}]]==1&],GraphHighlightStyle->"Dashed"]

CyclicEdgeConnectivity[GraphData[{"SierpinskiTetrahedron",2}],Debug->True,Method->"CanonicalGraph"]//Timing

CyclicEdgeConnectivity[GraphData[{"SierpinskiTetrahedron",2}],Debug->True,Method->"EdgeList"]//Timing

CyclicEdgeConnectivity[GraphData[{"SierpinskiTetrahedron",2}],Debug->True,Method->"EdgeList"]//Timing

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"CyclicEdgeConnectivity"],{n,10}]

StackedBook m×n

DeleteCases[
{#,GraphData[#,"NotationRules","StackedBook"],GraphData[#,"CyclicEdgeConnectivity"]}&/@GraphData["StackedBook",;;25],
{_,{1,_},2} (* Ladder *)|
{_,{2,_},3} (* 3x5 Grid *)|
{_,{_,1},0} (* Star *) |
{_,{_,2},0} (* Book *)|
{_,{_,3},0} (* Domino, 3x3 Grid, ... *)
]

GraphData/@{"DominoGraph",{"Grid",{3,3}},{"StackedBook",{3,3}}}

StackedPrism m×n

Table[GraphData[{"StackedPrism",{m,n}},"CyclicEdgeConnectivity"],{m,3,8},{n,5}]

GraphicsGrid[Partition[GraphData/@DeleteCases[GraphData["StackedPrism"],{"Cycle"|"Prism",_}],UpTo[5]]]

TextGrid[Partition[{Annotate[GraphData[#],ImageSize->Tiny],GraphData[#,"CyclicEdgeConnectivity"]/._Missing->X,First[nr=GraphData[#,"NotationRules","StackedPrism"]],nr}&/@DeleteCases[GraphData["StackedPrism"],{"Cycle"|"Prism",_}],UpTo[5]],Dividers->All]

StackedPrism m×n

DeleteCases[
Sort[{
GraphData[#,"NotationRules","StackedPrism"],
#,
GraphData[#,"CyclicEdgeConnectivity"]
}&/@GraphData["StackedPrism"]],
{{_,1},_,0}|
{{_,2},_,4}|
{{n_,5},_,n_}|
{{k_,_},_,k_}
]

StackedPrism n×n

seq=Table[GraphData[{"StackedPrism",{n,n}},"CyclicEdgeConnectivity"],{n,3,5}]

Star

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

seq=Table[GraphData[{"Star",n},"CyclicEdgeConnectivity"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"CyclicEdgeConnectivity"],{n,3,20}]

HighlightGraph[GraphData[{"Sun",#},"Graph",{"All","Labeled"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{4,1,{{2,5},{5,8},{5,6},{7,8},{6,7},{3,7}}},
{5,1,{{2,3},{2,4},{2,5},{2,7},{1,10},{1,5},{1,4},{1,3}}},
{6,1,{{3,9},{3,4},{3,5},{3,6},{3,1},{2,4},{2,5},{2,6},{2,7},{1,2}}}}

Sunlet

seq=Table[GraphData[{"Sunlet",n},"CyclicEdgeConnectivity"],{n,3,20}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"CyclicEdgeConnectivity"],{n,3,10}]

CyclicEdgeConnectivity[GraphData[{"TorusGrid",{4,4}}],Debug->True]

GraphData[{"TorusGrid",{3,3}},"EdgeCount"]

HighlightGraph[GraphData[{"TorusGrid",{#,#}},"Graph",{"All","Labeled"}][[#2]],GraphData[{"TorusGrid",{#,#}},"Edges"][[#3]],GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{4,6,10,12,13,18}},
{4,1,{15,17,19,20,23,25,27,28}}}

Transposition

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

seq=Table[GraphData[{"Transposition",n},"CyclicEdgeConnectivity"],{n,6}]

Triangular

seq=Table[GraphData[{"Triangular",n},"CyclicEdgeConnectivity"],{n,2,10}]

CyclicEdgeConnectivity[GraphData[{"Triangular",4}],Debug->True]

HighlightGraph[GraphData[{"Triangular",#},"Graph",{"All","Labeled"}][[#2]],GraphData[{"Triangular",#},"Edges"][[#3]],GraphHighlightStyle->"Dashed"]&@@@{
{4,1,{3,4,6,7,8,9}},
{5,1,{}}}

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"CyclicEdgeConnectivity"],{n,0,10}]

HighlightGraph[GraphData[{"TriangularGrid",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{{2,4},{2,5},{3,5},{3,6}}},
{4,1,{{2,4},{2,5},{3,5},{3,6}}},
{5,1,{{2,4},{2,5},{3,5},{3,6}}}}

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"CyclicEdgeConnectivity"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"CyclicEdgeConnectivity"],{n,9}]

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"CyclicEdgeConnectivity"],{n,20}]

FindSequenceFunction[Drop[seq,5],n-5]//Head//Timing

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"CyclicEdgeConnectivity"],{n,10}]

FindSequenceFunction[seq,n]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"CyclicEdgeConnectivity"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"CyclicEdgeConnectivity"],{n,1,20,2}]

HighlightGraph[GraphData[{"TriangularSnake",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{7,1,{{3,6},{6,7}}},
{9,1,{{3,4},{3,5}}},
{11,1,{{3,4},{3,5}}}}

Web

seq=Table[GraphData[{"Web",n},"CyclicEdgeConnectivity"],{n,3,20}]

HighlightGraph[GraphData[{"Web",#},"Graph",{"Labeled","All"}][[#2]],UndirectedEdge@@@#3,GraphHighlightStyle->"Dashed"]&@@@{
{3,1,{{1,4},{2,5},{3,6}}},
{4,1,{{1,5},{2,6},{3,7},{4,8}}},
{5,1,{{1,5},{6,10},{2,3},{7,8}}}}

Wheel

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

seq=Table[GraphData[{"Wheel",n},"CyclicEdgeConnectivity"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"CyclicEdgeConnectivity"],{n,2,20}]

FullSimplify[FindSequenceFunction[Rest@seq,n-2],n∈Integers]

Factor[%]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"CyclicEdgeConnectivity"],{n,20}]

Algorithms

HighlightGraph[g=GraphData[{"SierpinskiTetrahedron",2},"Graph"],Select[EdgeList[g],FreeQ[#,1]&&Length[Intersection[List@@#,{2,3,4}]]==1&],GraphHighlightStyle->"Dashed"]

"CanonicalGraph"

DeleteCases[Monitor[{g=#,GraphData[#,"CyclicEdgeConnectivity"],CyclicEdgeConnectivity[GraphData[#],Method->"CanonicalGraph"]}&/@GraphData[;;6],g],{_,x_,x_}]//Timing

CyclicEdgeConnectivity[GraphData["PetersenGraph"],Debug->True,Method->"CanonicalGraph"]//Timing

CyclicEdgeConnectivity[GraphData[{"SierpinskiTetrahedron",2}],Debug->True,Method->"CanonicalGraph"]//Timing

"EdgeList"

DeleteCases[Monitor[{g=#,GraphData[#,"CyclicEdgeConnectivity"],CyclicEdgeConnectivity[GraphData[#],Method->"EdgeList"]}&/@GraphData[;;6],g],{_,x_,x_}]//Timing

CyclicEdgeConnectivity[GraphData["PetersenGraph"],Debug->True,Method->"EdgeList"]//Timing

CyclicEdgeConnectivity[GraphData[{"SierpinskiTetrahedron",2}],Debug->True,Method->"EdgeList"]//Timing

"SymmetricallyDistinctEdges"

DeleteCases[Monitor[{g=#,GraphData[#,"CyclicEdgeConnectivity"],CyclicEdgeConnectivity[GraphData[#],Method->"SymmetricallyDistinctEdges"]}&/@GraphData[;;6],g],{_,x_,x_}]//Timing

CyclicEdgeConnectivity[GraphData["PetersenGraph"],Debug->True,Method->"SymmetricallyDistinctEdges"]//Timing