Minimal Edge Cut

Author

Eric W. Weisstein
December 18, 2024

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

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

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

Table

<<MathWorld`Graphs`

GraphDataCountTable["MinimalEdgeCutCount",{"Alkane"->016777,"Antiprism"->378922,"Barbell"->000225,"Book"->221905,"Centipede"->005408,"Complete"->000225,"CompleteBipartite"->379215,"Cycle"->000217,"CycleComplement"->378923,"Dipyramid"->077265,"Empty"->000004,"Gear"->054552,"Helm"->002522,"Ladder"->000384,"LadderRung"->000027,"MoebiusLadder"->378023,"Pan"->000124,"Path"->000027,"PlummerToft"->378924,"Prism"->307621,"Star"->000027,"Sun"->378796,"Sunlet"->000217,"TriangularHoneycombRook"->000295,"Wheel"->002061,"WheelComplement"->378923}]

Parametrized families

Alkane

A016777

Inferred for n > 5:

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

FindSequenceFunction[DeleteMissing@seq,n]

AlternatingGroupGraph

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

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"MinimalEdgeCutCount"],{n,10}]

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"MinimalEdgeCutCount"],{n,15}]

Antiprism

A378922

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

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

Length@DeleteMissing@seq+2

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{l,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindLinearRecurrence[Drop[DeleteMissing@seq,1]]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Apollonian

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Barbell

Inferred for n > 5:

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

FindSequenceFunction[DeleteMissing@seq,n]

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

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"MinimalEdgeCutCount"],{n,10}]

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Bishop n×n

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Book

A221905

Inferred for n > 5:

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

FindSequenceFunction[DeleteMissing@seq,n]

Table[3^n+3n,{n,20}]

Bruhat

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Camel n×n

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Centipede

A005408

Inferred for n > 7:

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

FindSequenceFunction[seq,n]

CocktailParty

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Complete

A000225

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

Inferred for n > 6:

seq=Table[GraphData[{"Complete",n},"MinimalEdgeCutCount"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

CompleteBipartite m×n

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

Sort@Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"MinimalEdgeCutCount"],
((((2^(m-1))-1))^2)+((((2^(n-1))-1))^2)+m+n
},{n,20},{m,n}],1]

CompleteBipartite n×n

A379215

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

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

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

Table[Piecewise[{{1,n==1}},2(((((2^(n-1))-1))^2)+n)],{n,20}]

FindLinearRecurrence[Rest@seq]

{1}~Join~LinearRecurrence[{8,-21,22,-8},{6,24,106,460},20]

gf=x FindGeneratingFunction[seq,x]

OEISGeneratingFunctionString[gf,x]

CoefficientList[Series[((1-2 x-3 (x^2)+18 (x^3)-8 (x^4))/((((-1+x))^2) (1-6 x+8 (x^2)))),{x,0,20}],x]

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

CrossedPrism

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

FindSequenceFunction[DeleteMissing@seq,n-1]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Crown

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Cycle

A000217

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

Inferred for n > 17:

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

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

FullSimplify[Subtract@@{(1/2) (-1+n) n,Binomial[n,2]}]

CycleComplement

A378923

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

Table[2^(n-1)-2n-1,{n,3,20}]

FindSequenceFunction[DeleteMissing@seq,n-2]

FindLinearRecurrence[Drop[seq,4]]

seq=={0,2,10,22}~Join~Table[2^(n-1)-2n-1,{n,7,20}]

seq=={0,2,10,22}~Join~LinearRecurrence[{4,-5,2},{49,111,237},14]

gf=x^3FindGeneratingFunction[DeleteMissing@seq,x]

CoefficientList[Series[((x(-2-2 x+8 (x^2)-7 (x^3)-5 (x^4)+6 (x^5)))/((((-1+x))^2) (-1+2 x))),{x,0,20}],x]

DiagonalIntersection

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Dipyramid

A077265

Inferred for n > 9:

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

Length@DeleteMissing@seq+2

Table[2^n+n(n-1),{n,3,20}]

FindSequenceFunction[DeleteMissing@seq,n-2]//FullSimplify

FindLinearRecurrence[DeleteMissing@seq]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

DorogovtsevGoltsevMendes

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

Empty

A000004

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

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

FibonacciCube

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Flower

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

FindSequenceFunction[DeleteMissing@seq,n-4]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

FoldedCube

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

FindSequenceFunction[DeleteMissing@seq,n-1]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Gear

A054552

Inferred for n > 8:

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Factor

Table[1-3 n+4 (n^2),{n,3,20}]

Limit[(x^n)+((n (x^2) (4 (x^n)-3x-1))/(x-1)),x->1]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"MinimalEdgeCutCount"],{n,10}]

Goldberg

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

FindSequenceFunction[DeleteMissing@seq,n-1]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Grid m×n

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

Grid n×n

Possibly A068416

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Grid k×m×n

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

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"MinimalEdgeCutCount"],
XXX
},{n,5},{m,n},{k,m}],2]

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

Grid n×n×n

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

HalvedCube

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Hanoi

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Helm

A002522

Inferred for n > 7:

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Factor

Hypercube

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

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

FindSequenceFunction[DeleteMissing@seq,n+1]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Keller

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

King n×n

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Knight m×n

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

Knight n×n

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Ladder

A000384

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

Inferred for n > 6:

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

FindSequenceFunction[DeleteMissing@seq,n]//Factor

LadderRung

A000027

Inferred for n > 16:

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

MengerSponge

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

MoebiusLadder

A378023

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

Inferred for n > 9:

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Factor

seq=Table[(2 (n^3)-6n^2+19n-9)n/6,{n,38}]

ToString[seq]//StringLength

FindLinearRecurrence[DeleteMissing@seq]//Factor

LinearRecurrence[{5,-10,10,-5,1},{1,7,24,66,155},20]

OEISRecurrenceIndexString[{5,-10,10,-5,1}]

OEISRecurrenceString[{5,-10,10,-5,1}]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

CoefficientList[Series[((-1-2 x+(x^2)-6 (x^3))/(((-1+x))^5)),{x,0,20}],x]

Mycielski

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Odd

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Pan

A000124

Inferred for n > 15:

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

FindSequenceFunction[DeleteMissing@seq,n-2]//FullSimplify

Path

A000027

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

Inferred for n > 17:

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

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

PathComplement

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

PlummerToft

A378924

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

seq==Table[5 2^n+(n+2)(n+7)/2,{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

Table[5 (2^n)+n (9+n)/2+7,{n,0,20}]

coef=FindLinearRecurrence[DeleteMissing@seq]

LinearRecurrence[{5,-9,7,-2},{22,38,65,113},{0,20}]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

CoefficientList[Series[((x (22-72 x+73 (x^2)-24 (x^3)))/((((-1+x))^3) (-1+2 x))),{x,0,20}],x]

Prism

A307621

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

Inferred for n > 7:

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Factor

Table[n(n-1)(2n^2-4n+15)/6+1,{n,3,25}]

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{l,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Queen n×n

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Rook n×n

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

RookComplement n×n

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

SierpinskiCarpet

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

SierpinskiSieve

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

SierpinskiTetrahedron

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

StackedBook

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

StackedPrism

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Star

A000027

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

Inferred for n > 17:

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

FindSequenceFunction[seq,n]//Factor

Sun

A378796

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

FindSequenceFunction[DeleteMissing@seq,n-2]//FullSimplify

Table[((((-1))^n)+(3^n)+2 n-2)/2,{n,20}]

FindLinearRecurrence[DeleteMissing@seq]

seq=LinearRecurrence[{4,-2,-4,3},{1,6,15,44},20]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

OEISGeneratingFunctionString[gf,x]

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

CoefficientList[Series[((-1-2 x+7 (x^2))/((((-1+x))^2) (-1+2 x+3 (x^2)))),{x,0,20}],x]

Sunlet

A000217

Inferred for n > 8:

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

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

TorusGrid n×n

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Transposition

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

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Trapezohedron

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

A077263

Inferred for n > 6:

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

seq==Table[4 n (n-1)+RootSum[-1-#-3 #^2+#^3&,#^n&],{n,3,20}]

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Triangular

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

FindSequenceFunction[DeleteMissing@seq,n-1]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

TriangularGrid

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

FindSequenceFunction[DeleteMissing@seq,n+1]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

TriangularHoneycombAcuteKnight

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

TriangularHoneycombBishop

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

TriangularHoneycombObtuseKnight

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

TriangularHoneycombQueen

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

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

FindSequenceFunction[seq,n]

TriangularHoneycombRook

A000295

seq=Table[GraphData[{"TriangularHoneycombRook",n},"MinimalEdgeCutCount"],{n,10}]

TriangularSnake

Inferred for n > 11:

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

FindSequenceFunction[DeleteMissing@seq,(n+1)/2]//FullSimplify

Table[(3/2) (n-1),{n,1,20,2}]

Web

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Wheel

A002061

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

Inferred for n > 9:

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

FindSequenceFunction[DeleteMissing@seq,n-3]//FullSimplify

Factor[3+(-3+n) n]

Table[n(n-3)+3,{n,4,20}]

WheelComplement

A378923(n+1)

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

2^(n-1)-2*n-1/.n->n-1

Table[-1+(2^(-2+n))-2 (-1+n),{n,4,20}]

FindSequenceFunction[DeleteMissing@seq,n-3]

FindLinearRecurrence[Drop[seq,4]]

gf=FindGeneratingFunction[DeleteMissing@seq,x]

WhiteBishop n×n

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

FindSequenceFunction[DeleteMissing@seq,n-1]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"MinimalEdgeCutCount"],{n,10}]

FindSequenceFunction[DeleteMissing@seq,n]//Head

FindLinearRecurrence[DeleteMissing@seq]//Head

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head