Cyclic Edge Cut

Author

Eric W. Weisstein
November 27, 2024

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

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

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

Figure

(cycliccuts=FindCyclicEdgeCuts[GraphData["P"]])//Timing

edges=EdgeList[GraphData["P"]];

g1=HighlightGraph[Annotate[GraphData["PetersenGraph"],{VertexStyle->Black,EdgeStyle->Black}],UndirectedEdge@@@edges[[#]],GraphHighlightStyle->"Dashed",ImageSize->150]&/@cycliccuts

g2=HighlightGraph[Annotate[GraphData["PetersenGraph"],{VertexStyle->Black,EdgeStyle->Black}],Style[UndirectedEdge@@@edges[[#]],White],EdgeStyle->Black,ImageSize->150]&/@cycliccuts

Grid[Transpose[{g1,Table[Style["→",40],6],g2}][[{2,3}]],Alignment->Center]

Small graphs with a cyclic edge cut

(small=SplitBy[Sort[{GraphData[#,"M"],#}&/@Select[GraphData[;;6],GraphData[#,"CyclicEdgeCuts"]=!={}&]],First])//Column

small[[All,All,2]]

FindMinimumCyclicEdgeCut[GraphData[#],All]&/@{{"Barbell",3},"TransSquareWithTwoTriangles",{"Matchstick",{8,19}}}//Column

GraphicsGrid[
Map[
With[{g=StyleGraphs@GraphData[#],e=GraphData[#,"Edges"]},
Annotate[g,{EdgeStyle->Thread[(e[[cut=FindMinimumCyclicEdgeCut[g][[1]]]]->Directive[Dashing[.02]])],PlotLabel->Row[{Subscript["λ",Style["c",Italic]],"==",Length[cut]}," "]}]
]&,
small[[;;2,All,2]],
{2}],
Dividers->All,BaseStyle->InsetBoxOptions->{BaseStyle->Directive[FontFamily->"Times",Black,16]}]

Disconnected

"2C3"

FindCyclicEdgeCuts[GraphData["2C3"]]

GraphData["2C3","CyclicEdgeCuts"]

GraphData["2C3","CyclicEdgeCutCount"]

GraphData["2C3","CyclicEdgeConnectivity"]

GraphData["2C3","MinimumCyclicEdgeCuts"]

GraphData["2C3","MinimumCyclicEdgeCutCount"]

"3C3"

EdgeLabeledGraph[GraphData["3C3"]]

FindCyclicEdgeCuts[GraphData["3C3"]]

GraphData["3C3","CyclicEdgeCutIndices"]

GraphData["3C3","CyclicEdgeCutCount"]

GraphData["3C3","CyclicEdgeConnectivity"]

GraphData["3C3","MinimumCyclicEdgeCuts"]

GraphData["3C3","MinimumCyclicEdgeCutCount"]

"TwoPaws"

EdgeLabeledGraph[GraphData["TwoPaws"]]

FindCyclicEdgeCuts[GraphData["TwoPaws"]]

GraphData["TwoPaws","CyclicEdgeCutIndices"]

GraphData["TwoPaws","CyclicEdgeCutCount"]

GraphData["TwoPaws","CyclicEdgeConnectivity"]

GraphData["TwoPaws","MinimumCyclicEdgeCuts"]

GraphData["TwoPaws","MinimumCyclicEdgeCutCount"]

GraphDataCountTable

GraphDataCountTable["CyclicEdgeCutCount",{"Antiprism"->378310,"Barbell"->378431,"Complete"->378324,"Ladder"->378296,"MoebiusLadder"->378312,"Prism"->378311}]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"CyclicEdgeCutCount"],{n,10}]

AlternatingGroupGraph

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

Andrasfai

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

Antelope n×n

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

Antiprism

A378310

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

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

Do[
Print[{gn={"Antiprism",n},Length@FindCyclicEdgeCuts[GraphData[gn]]//Timing,MaxMemoryUsed[]/10^9. GB}],
{n,3,5}]

Apollonian

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

Barbell

A378431

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

Bishop n×n

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

BlackBishop n×n

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

Book

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

Bruhat

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

Camel n×n

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

Centipede

seq=Table[GraphData[{"Centipede",n},"CyclicEdgeCutCount"],{n,10}]

CocktailParty

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

Complete

A378324

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

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

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

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

FindLinearRecurrence[DeleteCases[seq,0]]//Head//Timing

ComputeCyclicEdgeCuts[Table[{"Complete",n},{n,8}],x];

E.g.f.: (exp(B(x)-T(x))-(B(x)-T(x))-1)*exp(T(x)-1) where B(x) is the e.g.f. of A001187 and T(x) is the e.g.f. of A000272. - Andrew Howroyd, Nov 26 2024

(PARI) seq(n)={my(t=sum(k=1, n, k^(k-2)*x^k/k!, O(x*x^n)), c=log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, O(x*x^n)))-t); Vec(serlaplace((exp(c)-1-c)*exp(t)), -n)} \\ Andrew Howroyd, Nov 26 2024

A001187

Number of connected labeled graphs with n nodes.

Table[n! SeriesCoefficient[1+Log[Sum[2^(k(k-1)/2) x^k/k!,{k,0,n}]],{x,0,n}],{n,10}]

Rest@CoefficientList[Series[1+Log[Sum[2^(k(k-1)/2) x^k/k!,{k,0,100}]],{x,0,10}],x]Range[10]!

Sum[2^(k(k-1)/2) x^k/k!,{k,0,n}]

A000272

Number of trees on n labeled nodes: n^(n-2) with a(0)=1.

Table[n^(n-2),{n,10}]

Table[n! SeriesCoefficient[1-LambertW[-x]-LambertW[-x]^2/2,{x,0,n}],{n,10}]

SeriesCoefficient[1-LambertW[-x]-LambertW[-x]^2/2,{x,0,n}]

Rest@CoefficientList[Series[1-LambertW[-x]-LambertW[-x]^2/2,{x,0,10}],x]Range[10]!

B[x_]:=1+Log[Sum[2^(k(k-1)/2) x^k/k!,{k,0,97}]]
T[x_]:=1-LambertW[-x]-LambertW[-x]^2/2

ser0=Rest@CoefficientList[Series[(Exp[B[x]-T[x]]-(B[x]-T[x])-1)Exp[T[x]-1],{x,0,100}],x]Range[100]!;

B[x_]:=1+Log[Sum[2^(k(k-1)/2) x^k/k!,{k,0,500}]]
T[x_]:=1-LambertW[-x]-LambertW[-x]^2/2

ser1=Rest@CoefficientList[Series[(Exp[B[x]-T[x]]-(B[x]-T[x])-1)Exp[T[x]-1],{x,0,100}],x]Range[100]!;

ser0===ser1

BFile[ser1=Rest@CoefficientList[Series[(Exp[B[x]-T[x]]-(B[x]-T[x])-1)Exp[T[x]-1],{x,0,100}],x]Range[100]!,378324]

B[x_]:=1+Log[Sum[2^(k(k-1)/2) x^k/k!,{k,0,200}]]
T[x_]:=1-LambertW[-x]-LambertW[-x]^2/2

ser2=Rest@CoefficientList[Series[(Exp[B[x]-T[x]]-(B[x]-T[x])-1)Exp[T[x]-1],{x,0,100}],x]Range[100]!;

ser1===ser2

B[x_]:=1+Log[Sum[2^(k(k-1)/2) x^k/k!,{k,0,100}]]
T[x_]:=1-LambertW[-x]-LambertW[-x]^2/2

ser3=Rest@CoefficientList[Series[(Exp[B[x]-T[x]]-(B[x]-T[x])-1)Exp[T[x]-1],{x,0,100}],x]Range[100]!;

ser3===ser2

Binomial[k,2]

With[{n=20},
B[x_]:=1+Log[Sum[2^Binomial[k,2] x^k/k!,{k,0,n}]];
T[x_]:=1-LambertW[-x]-LambertW[-x]^2/2;
Rest@CoefficientList[Series[(Exp[B[x]-T[x]]-(B[x]-T[x])-1)Exp[T[x]-1],{x,0,n}],x]Range[n]!
]

CompleteBipartite n×n

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

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

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"CyclicEdgeCutCount"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

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

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

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"CyclicEdgeCutCount"],
3Max[k,m,n]/2
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

seq=Table[GraphData[{"CubeConnectedCycle",n},"CyclicEdgeCutCount"],{n,3,8}]

Cycle

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

seq=Table[GraphData[{"Cycle",n},"CyclicEdgeCutCount"],{n,3,30}]

CycleComplement

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

DiagonalIntersection

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

Dipyramid

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

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"CyclicEdgeCutCount"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"CyclicEdgeCutCount"],{n,3,20}]

Empty

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

seq=Table[GraphData[{"Empty",n},"CyclicEdgeCutCount"],{n,30}]

FibonacciCube

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

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"CyclicEdgeCutCount"],{n,20}]

Flower

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

FoldedCube

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

Gear

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

Giraffe n×n

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

Goldberg

seq=Table[GraphData[{"Goldberg",n},"CyclicEdgeCutCount"],{n,3,20}]

Grid n×n

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

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

Grid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"CyclicEdgeCutCount"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

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

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

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"CyclicEdgeCutCount"],
XXX
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

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

Hanoi

seq=Table[GraphData[{"Hanoi",n},"CyclicEdgeCutCount"],{n,6}]

Helm

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

Hypercube

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

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

Keller

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

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

King n×n

seq=Table[GraphData[{"King",{n,n}},"CyclicEdgeCutCount"],{n,20}]

King m×n

Entity["Graph",{"King",{m,n}}]["CyclicEdgeCutCount"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"CyclicEdgeCutCount"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

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

Knight m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"CyclicEdgeCutCount"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Ladder

A378296

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

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

Length@DeleteMissing@seq

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

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

FindLinearRecurrence[Drop[seq,3]]//Head//Timing

LadderRung

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

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"CyclicEdgeCutCount"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"CyclicEdgeCutCount"],{n,15}]

MengerSponge

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

MoebiusLadder

A378312

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

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

Mycielski

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

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

Odd

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

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

Pan

seq=Table[GraphData[{"Pan",n},"CyclicEdgeCutCount"],{n,3,20}]

Path

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

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

PathComplement

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

Pell

seq=Table[GraphData[{"Pell",n},"CyclicEdgeCutCount"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"CyclicEdgeCutCount"],{n,20}]

Prism

A378311

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

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

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"CyclicEdgeCutCount"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"CyclicEdgeCutCount"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"CyclicEdgeCutCount"],{n,20}]

SierpinskiCarpet

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

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"CyclicEdgeCutCount"],{n,7}]

SierpinskiTetrahedron

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

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"CyclicEdgeCutCount"],{n,5}]

StackedBook

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

StackedPrism

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

Star

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

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

Sun

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

Sunlet

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

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"CyclicEdgeCutCount"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"CyclicEdgeCutCount"],{n,3,20}]

Transposition

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

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

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["CyclicEdgeCutCount"]

seq=Table[GraphData[{"Trapezohedron",n},"CyclicEdgeCutCount"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"CyclicEdgeCutCount"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"CyclicEdgeCutCount"],{n,0,20}]

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"CyclicEdgeCutCount"],{n,20}]

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"CyclicEdgeCutCount"],{n,20}]

TriangularHoneycombRook

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

TriangularSnake

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

Web

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

Wheel

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

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

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"CyclicEdgeCutCount"],{n,4,20}]

WhiteBishop n×n

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

WhiteCamel n×n

seq=Table[GraphData[{"WhiteCamel",{n,n}},"CyclicEdgeCutCount"],{n,{5}}]

Zebra n×n

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

Algorithms

EdgeLabeledGraph[g_Graph]:=Annotate[g,EdgeLabels->Thread[EdgeList[g]->(Text[Row[{" ",#," "}],Background->White]&/@Range[EdgeCount[g]])]]

<<MathWorld`Graphs`

AtLeastNTrue[CyclicGraphQ, cc, 2]

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

Count[AcyclicGraphQ /@ cc, False] > 1

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

Select

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