Minimum Edge Cut

Author

Eric W. Weisstein
January 23, 2024

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

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

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

Table

GraphDataCountTable["MinimumEdgeCutCount",Join[
{"Alkane"->016777,"Andrasfai"->016789,"Apollonian"->000244,"Book"->008585,"Centipede"->005408,"Complete"->184985,"CompleteTripartite"->008585,"CrossedPrism"->008586,"CubeConnectedCycle"->036289,"Cycle"->000217,"FibonacciCube"->352247,"Flower"->008586,"FoldedCube"->000079,"Goldberg"->008590,"Hanoi"->008585,"Hypercube"->000079,"TorusGrid"->000290,"Triangular"->253145,"TriangularHoneycombQueen"->000217,"TriangularSnake"->008585},

(* 1, 2, ... *)
Thread[{"CycleComplement","Dipyramid","Gear","Helm","Ladder","Path","PathComplement","Star","Sun","Sunlet","TriangularHoneycombBishop","Web","Wheel"}->000027],

(* 2, 4, 6, ... *)
Thread[{"Antiprism","BlackBishop","CocktailParty","CompleteBipartite","Crown","MoebiusLadder","Prism","StackedBook","WhiteBishop"}->005843],

(* 0 *)Thread[{"Empty","LadderRung","TriangularHoneycombAcuteKnight","TriangularHoneycombRook"}->000007],
(* 1 *)Thread[{"Barbell","Pan"}->000012],
(* 3 *)Thread[{"SierpinskiSieve","TriangularGrid","TriangularHoneycombObtuseKnight"}->010701],
(* 4 *)Thread[{"Giraffe",{"Grid",2},"King","Knight"}->010709],
(* 6 *)Thread[{"HexagonalGrid"}->008588]
(*
(* 8 *)Thread[
(*{{"Grid",3}}->XXX Not in OEIS *)]
(* 16 *)
(* 32 *)
*)
]]

Parametrized families

<<MathWorld`Graphs`

data=Partition[#,UpTo[10]]&/@Table[With[{gn={"Complete",n}},HighlightGraph[GraphData[gn],#,GraphHighlightStyle->"Dotted"]&/@GraphData[gn,"MinimumEdgeCuts"]],{n,6,8}];
GraphicsGrid[Flatten[data,1],Dividers->{Thread[{1,-1}->Thick],Thread[(1+Accumulate[Prepend[Length/@data,0]])->Thick]}]

AlternatingGroupGraph

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

Andrasfai

Inferred for n > 10:

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

Antelope n×n

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

Antiprism

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

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

FindSequenceFunction[seq,n-2]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"MinimumEdgeCutCount"],{n,6}]

Table[Piecewise[{{4,n==1}},(3^(n-1))],{n,6}]

Barbell

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

data=Partition[#,UpTo[10]]&/@Table[With[{gn={"Barbell",n}},HighlightGraph[GraphData[gn],#,GraphHighlightStyle->"Dotted"]&/@GraphData[gn,"MinimumEdgeCuts"]],{n,3,6}];
GraphicsGrid[Flatten[data,1],Dividers->{Thread[{1,-1}->Thick],Thread[(1+Accumulate[Prepend[Length/@data,0]])->Thick]}]

BlackBishop n×n

Inferred for n > 10:

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

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"MinimumEdgeCutCount"],{n,10}]

Book

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

FindSequenceFunction[seq,n]

Bruhat

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

FindSequenceFunction[seq,n]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"MinimumEdgeCutCount"],{n,10}]

CocktailParty

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

Complete

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

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

Table[Piecewise[{{0,n==1},{1,n==2}},n],{n,30}]==seq

CompleteBipartite m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"MinimumEdgeCutCount"],
Piecewise[{{1,m==n==1},{6,m==n==2},{2n,m==n}},Max[m,n]]
},{n,20},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

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

Table[Piecewise[{{1,n==1},{6,n==2}},2n],{n,20}]

CompleteTripartite k×m×n

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

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"MinimumEdgeCutCount"],
Piecewise[{{3k,k==m==n},{2Max[k,m,n],Max[k,m,n]==k m n/(Max[k,m,n]Min[k,m,n])}},Max[k,m,n]]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

DeleteCases[%,{_,_Missing,_}]

CompleteTripartite n×n×n

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

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

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"MinimumEdgeCutCount"],{n,2,10}]

FindSequenceFunction[seq,n-1]//Factor

Crown

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

data=Partition[#,UpTo[10]]&/@Table[With[{gn={"Crown",n}},HighlightGraph[GraphData[gn,"Graph","Circular"][[1]],#,GraphHighlightStyle->"Dotted"]&/@GraphData[gn,"MinimumEdgeCuts"]],{n,3,6}];
GraphicsGrid[Flatten[data,1],Dividers->{Thread[{1,-1}->Thick],Thread[(1+Accumulate[Prepend[Length/@data,0]])->Thick]}]

CubeConnectedCycle

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

Inferred for n>6

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

FindSequenceFunction[Rest@DeleteMissing@seq,n-2]

Table[Piecewise[{{32,n==3}},n (2^n)],{n,3,8}]

Cycle

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

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

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

Table[Binomial[n,2],{n,3,20}]

CycleComplement

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

DiagonalIntersection

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

Dipyramid

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

gf=(x^3)FindGeneratingFunction[seq,x]

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

DorogovtsevGoltsevMendes

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

FindSequenceFunction[Rest@seq,n-1]//Factor

FibonacciCube

A352247

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

data=Partition[#,UpTo[10]]&/@Table[With[{gn={"FibonacciCube",n}},HighlightGraph[Annotate[GraphData[gn],VertexSize->Medium],#,GraphHighlightStyle->"Dotted"]&/@GraphData[gn,"MinimumEdgeCuts"]],{n,6}];
GraphicsGrid[Flatten[data,1],Dividers->{Thread[{1,-1}->Thick],Thread[(1+Accumulate[Prepend[Length/@data,0]])->Thick]}]

Flower

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

FoldedCube

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

Gear

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

FindSequenceFunction[seq,n-2]

Giraffe n×n

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

Goldberg

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

Table[Piecewise[{{25,n==3}},8n],{n,3,20}]

Grid m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"MinimumEdgeCutCount"],
Piecewise[{{Max[m,n]-1,Min[m,n]==1},{6,m==n==2},{Max[m,n]+3,Min[m,n]==2}},4]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

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

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

Table[Piecewise[{{0,n==1},{6,n==2}},4],{n,20}]==seq

Grid k×m×n

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

DeleteCases[Select[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"MinimumEdgeCutCount"],
Piecewise[{
{Max[k,m,n]-1,k m n==Max[k,m,n]},
{6,Max[k,m,n]==2&&k m n==4},
{Max[k,m,n]+3,Min[k,m,n]==1&&k m n/Max[k,m,n]==2},
{4,Min[k,m,n]==1}
},8]
},{n,10},{m,n},{k,m}],2],FreeQ[GraphData]],{_,x_,x_}]//Quiet

Tally[GraphData[{"Grid",{2,3,4}},"DistanceMatrix"]//Normal//Flatten]

Grid n×n×n

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

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

Table[Piecewise[{{0,n==1}},8],{n,10}]

HalvedCube

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

Hanoi

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

Helm

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

FindSequenceFunction[seq,n-2]

Hypercube

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

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

data=Partition[#,UpTo[10]]&/@Table[With[{gn={"Hypercube",n}},HighlightGraph[GraphData[gn],#,GraphHighlightStyle->"Dotted"]&/@GraphData[gn,"MinimumEdgeCuts"]],{n,5}];
GraphicsGrid[Flatten[data,1],Dividers->{Thread[{1,-1}->Thick],Thread[(1+Accumulate[Prepend[Length/@data,0]])->Thick]}]

Keller

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

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

King n×n

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

Knight m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"MinimumEdgeCutCount"],
Piecewise[{{0,Min[m,n]<3||m==n==3},{15,Min[m,n]==3&&Max[m,n]==4},{8,Min[m,n]==3}},4]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

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

Ladder

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

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

Table[Piecewise[{{1,n==1},{6,n==2}},n+3],{n,20}]

LadderRung

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

MengerSponge

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

Table[2 (6^n),{n,3}]

MoebiusLadder

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

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

FindSequenceFunction[seq,n-2]

Mycielski

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

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

Odd

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

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

Path

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

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

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

PathComplement

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

Pell

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

Prism

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

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

Table[Piecewise[{{7,n==3}},2n],{n,3,25}]

Queen n×n

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

Rook m×n

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"Rook",{m,n}},"MinimumEdgeCutCount"],
m n
},{m,10},{n,m,10}],1],{_,x_,x_}]

Rook n×n

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

RookComplement n×n

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

SierpinskiCarpet

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

Table[Piecewise[{{28,n==1}},32 (3^(n-2))],{n,4}]

SierpinskiSieve

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

data=Partition[#,UpTo[10]]&/@Table[With[{gn={"SierpinskiSieve",n}},HighlightGraph[GraphData[gn],#,GraphHighlightStyle->"Dotted"]&/@GraphData[gn,"MinimumEdgeCuts"]],{n,3}];
GraphicsGrid[Flatten[data,1],Dividers->{Thread[{1,-1}->Thick],Thread[(1+Accumulate[Prepend[Length/@data,0]])->Thick]}]

SierpinskiTetrahedron

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

data=Partition[#,UpTo[10]]&/@Table[With[{gn={"SierpinskiTetrahedron",n}},HighlightGraph[GraphData[gn,"Graph","3D"],#,GraphHighlightStyle->"Dotted"]&/@GraphData[gn,"MinimumEdgeCuts"]],{n,2}];
GraphicsGrid[Flatten[data,1],Dividers->{Thread[{1,-1}->Thick],Thread[(1+Accumulate[Prepend[Length/@data,0]])->Thick]}]

StackedBook

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

StackedPrism

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

Star

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

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

FindSequenceFunction[seq,n]//Factor

Sun

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

Sunlet

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

FindSequenceFunction[seq,n-2]

TorusGrid m×n

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"TorusGrid",{m,n}},"MinimumEdgeCutCount"],
m n
},{m,3,10},{n,m,10}],1],{_,x_,x_}]

TorusGrid n×n

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

Transposition

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

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

Trapezohedron

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

Triangular

A253145

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

Table[Piecewise[{{0,n==1}},Binomial[n,2]],{n,2,20}]

TriangularGrid

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

data=Partition[#,UpTo[10]]&/@Table[With[{gn={"TriangularGrid",n}},HighlightGraph[GraphData[gn],#,GraphHighlightStyle->"Dashed"]&/@GraphData[gn,"MinimumEdgeCuts"]],{n,3}];
GraphicsGrid[Flatten[data,1],Dividers->{Thread[{1,-1}->Thick],Thread[(1+Accumulate[Prepend[Length/@data,0]])->Thick]}]

TriangularHoneycombAcuteKnight

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

Do[Print[{gn={"TriangularHoneycombAcuteKnight",n},FindMinimumEdgeCut[GraphData[{"TriangularHoneycombAcuteKnight",n}],All]//Timing}],{n,3,20}]

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

Table[Piecewise[{{0,n==1}},Binomial[n+1,2]],{n,10}]

TriangularHoneycombRook

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

Do[Print[{gn={"TriangularHoneycombRook",n},FindMinimumEdgeCut[GraphData[{"TriangularHoneycombRook",n}],All]//Timing}],{n,2,20}]

TriangularSnake

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

Web

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

Wheel

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

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

Table[Piecewise[{{4,n==4}},n-1],{n,4,20}]

WheelComplement

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

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"MinimumEdgeCutCount"],{n,2,10}]

Zebra n×n

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