Maximum Independent Vertex Set

Author

Eric W. Weisstein
February 9, 2024

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

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

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

Figure

New

GraphicsRow[HighlightGraph[SetProperty[#,{VertexSize->{"Scaled",.06},System`VertexStyle->Black,System`EdgeStyle->Black}],Style[FindIndependentVertexSet[#],Directive[Red]]]&/@(GraphData/@{{"Wheel",8},"UtilityGraph","PetersenGraph","FruchtGraph"}),ImageSize->400]

Combinatorica

ShowGraphArray[Highlight[#,MaximumIndependentSet[#],HighlightedVertexColors->{Red},HighlightedVertexStyle->Disk[.1]]&/@{Wheel[8],UtilityGraph,PetersenGraph,FruchtGraph},VertexColor->Black,VertexStyle->Disk[.1]]

Counts

FullTally[l_List]:=Module[{t=Sort[Tally[l]],f,r},
If[(f=t[[All,1]])===(r=Range@@f[[{1,-1}]]),t,Sort[Join[t,{#,0}&/@Complement[r,f]]]]
]

(FullTally/@(values=Table[Length[FindAllMaximumIndependentVertexSets[#]]&/@Graphs[n],{n,8}]))//Column

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/MaximumIndependentVertexSetCount"];

(tallies=FullTally[#][[All,2]]&/@(values=Get/@FileNames["*.m"]))//Column

Flatten[tallies]

A000088

Total/@tallies

Length/@tallies

Not in OEIS:

Total/@values

Parametrized families

GraphDataCountTable["MaximumIndependentVertexSetCount",{"Alkane"->000012,"Antelope"->370198,"Book"->007395,"CrossedPrism"->007395,"DiagonalIntersection"->292923,"Empty"->000012,"Gear"->000012,"HalvedCube"->360685,"Hanoi"->297536,"Helm"->000012,"Hypercube"->007395,"King"->018807,"Ladder"->007395,"Rook"->000142,"SierpinskiTetrahedron"->360131,"Sun"->000012,"Triangular"->133221,"TriangularGrid"->297557,"TriangularHoneycombAcuteKnight"->297537,"TriangularHoneycombBishop"->000012,"TriangularHoneycombObtuseKnight"->299709,"TriangularHoneycombQueen"->289893,"TriangularHoneycombRook"->000142}]

Counts

<<MathWorld`Graphs`

Andrasfai

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

FindSequenceFunction[seq,n]

Antelope n×n

A370198

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

Table[GraphData[{"Antelope",{n,n}},"α"],{n,15}]

Table[GraphData[{"Antelope",{n,n}},"V"],{n,15}]

Table[Length@FindIndependentVertexSet[AntelopeGraph[n,n],{GraphData[{"Antelope",{n,n}},"α"]},All],{n,8}]//Timing

Do[Print[{gn={"Antelope",{n,n}},MaximumIndependentVertexSetCount[GraphData[gn]]//Timing}],{n,20}]

Do[Print[{gn={"Antelope",{n,n}},MaximumIndependentVertexSetCount[GraphData[gn]]//Timing}],{n,16,20}]

Antiprism

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

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

Apollonian

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

Table[GraphData[{"Apollonian",n},"α"],{n,6}]

Table[GraphData[{"Apollonian",n},"V"],{n,6}]

Table[Length@FindIndependentVertexSet[ApollonianGraph[n],{GraphData[{"Apollonian",n},"α"]},All],{n,4}]//Timing

Do[Print[{gn={"Apollonian",n},MaximumIndependentVertexSetCount[GraphData[gn]]//Timing}],{n,6}]

Do[Print[{gn={"Apollonian",n},FindAllMaximumIndependentVertexSets[GraphData[gn]]//Timing}],{n,6}]

Barbell

A005563

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

FindSequenceFunction[seq,n-2]//Factor

Bishop n×n

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

FindSequenceFunction[Rest@seq,n-1]

BlackBishop n×n

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

FullSimplify[FindSequenceFunction[DeleteMissing@Rest@seq,n-1],n∈Integers&&n>0]

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

Book

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

Camel n×n

Table[GraphData[{"Camel",{n,n}},"MaximumIndependentVertexSetCount"],{n,20}]

Do[Print[{gn={"Camel",{n,n}},MaximumIndependentVertexSetCount[GraphData[gn]]//Timing}],{n,20}]

Centipede

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

FindSequenceFunction[seq,n]//FullSimplify

Fibonacci[Range[10]+2]

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

DeleteCases[Block[{m,n},{
{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],
GraphData[#,"MaximumIndependentVertexSetCount"],
Piecewise[{{2, m == n}}, 1]
}&/@GraphData["CompleteBipartite"]],{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

DeleteCases[Block[{k,m,n},{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],
Piecewise[{{3, k == m == n}, {2, k == m == Max[k, m, n] || m == n == Max[k, m, n] || n == k == Max[k, m, n]}}, 1],
GraphData[#,"MaximumIndependentVertexSetCount"]
}&/@GraphData["CompleteTripartite"]],{_,x_,x_}]

CompleteTripartite n×n×n

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

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

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

Table[GraphData[{"CubeConnectedCycle",n},"α"],{n,3,8}]

Table[GraphData[{"CubeConnectedCycle",n},"V"],{n,3,8}]

Do[Print[{gn={"CubeConnectedCycle",n},MaximumIndependentVertexSetCount[CubeConnectedCycleGraph[n]]//Timing}],{n,8}]

Cycle

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

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

DiagonalIntersection

A292923

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

Do[Print[{gn={"DiagonalIntersection",n},MaximumIndependentVertexSetCount[PolygonDiagonalIntersectionGraph[n]]//Timing}],{n,3,14}]

DorogovtsevGoltsevMendes

Inferred for n == 7:

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

Table[With[{gn={"DorogovtsevGoltsevMendes",n}},HighlightGraph[Annotate[GraphData[gn,"Graph"],VertexSize->{"Scaled",.03}],GraphData[gn,"MaximumIndependentVertexSets"][[1]]]],{n,5}]

Table[GraphData[{"DorogovtsevGoltsevMendes",n},"V"],{n,7}]

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

Do[Print[{gn={"DorogovtsevGoltsevMendes",n},MaximumIndependentVertexSetCount[GraphData[gn]]//Timing}],{n,7}]

Do[Print[{gn={"DorogovtsevGoltsevMendes",n},FindAllMaximumIndependentVertexSets[GraphData[gn]]//Timing}],{n,7}]

Empty

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

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

FibonacciCube

Computed up to n=9; inferred beyond

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

Table[GraphData[{"FibonacciCube",n},"α"],{n,15}]

Table[GraphData[{"FibonacciCube",n},"V"],{n,15}]

Table[Length@FindIndependentVertexSet[FibonacciCubeGraph[n],{GraphData[{"FibonacciCube",n},"α"]},All],{n,8}]//Timing

Table[If[Mod[n,3]==1,2,1],{n,15}]

FoldedCube

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

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

FindLinearRecurrence[DeleteMissing@seq]//Head//Timing

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

Table[GraphData[{"FoldedCube",n},"α"],{n,2,10}]

Table[GraphData[{"FoldedCube",n},"V"],{n,2,10}]

Table[Length@FindIndependentVertexSet[FoldedCubeGraph[n],{GraphData[{"FoldedCube",n},"α"]},All],{n,2,7}]//Timing

Table[If[Mod[n,2]==0,2,(2^(n-1))],{n,2,10}]

Do[Print[{gn={"FoldedCube",n},MaximumIndependentVertexSetCount[FoldedCubeGraph[n]]//Timing}],{n,2,10}]

Fiveleaper n×n

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

Do[Print[{gn={"Fiveleaper",{n,n}},MaximumIndependentVertexSetCount[GraphData[gn]]//Timing}],{n,20}]

Do[Print[{gn={"Fiveleaper",{n,n}},FindAllMaximumIndependentVertexSets[GraphData[gn]]//Timing}],{n,20}]

Gear

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

Giraffe n×n

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

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

Table[Ceiling[n^2/2],{n,20}]

Do[Print[{gn={"Giraffe",{n,n}},MaximumIndependentVertexSetCount[GiraffeGraph[n,n]]//Timing}],{n,20}]

GraphData[{"Giraffe",{11,11}},"Connected"]

IndependenceNumber@GraphData[{"Giraffe",{11,11}}]//Timing

Print[{#,FindIndependentVertexSet[GraphData[#],{61},1]//Timing}]&/@{{"Giraffe",{11,11}}};

Print[{#,FindIndependentVertexSet[GraphData[#],{61},2]//Timing}]&/@{{"Giraffe",{11,11}}};

Goldberg

Inferred for n > 15:

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

DeleteMissing@seq[[1;;;;2]]

FindSequenceFunction[%,(n-1)/2]//Simplify

DeleteMissing@seq[[2;;;;2]]

FindSequenceFunction[%,n/2-1]//Simplify

Table[Piecewise[{{(2^((3+n)/2)) n,Mod[n,2]==1},{(2^(2+(n/2))),Mod[n,2]==0}}],{n,3,20}]

Grid m×n

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

Table[GraphData[{"Grid",{m,n}},"MaximumIndependentVertexSetCount"],{n,10},{m,n}]//Column

Table[GraphData[{"Grid",{m,n}},"MaximumIndependentVertexSetCount"],{n,10},{m,n}]//Flatten

Table[Piecewise[{
{n/2+1,Mod[Max[m,n],2]==0&&Min[m,n]==1},
{2,Mod[m n,2]==0}
},1],{n,10},{m,n}]//Column

Grid n×n

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

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

Grid k×m×n

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

Table[GraphData[{"Grid",{k,m,n}},"MaximumIndependentVertexSetCount"],{n,5},{m,n},{k,m}]//Column

Table[Piecewise[{
{n/2+1,Mod[Max[k,m,n],2]==0&&(k==m==1||m==n==1||n==k==1)},
{2,Mod[k m n,2]==0}
},1],{n,10},{m,n},{k,m}]//Column

Grid n×n×n

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

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

HalvedCube

A360685

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

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

FindLinearRecurrence[DeleteMissing@seq]//Head//Timing

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

Do[Print[{gn={"HalvedCube",n},MaximumIndependentVertexSetCount[HalvedCubeGraph[n]]//Timing}],{n,10}]

Table[With[{g=GraphPower[HypercubeGraph[n-1],2]},Length[FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],All]]],{n,8}]

Hanoi

A297536

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

FindSequenceFunction[DeleteMissing@seq,n]

{1,3,3,1}.#&/@NestList[Function[{h,i,j,k},{h^3+6 h^2 i+9 h i^2+3 h^2 j+2 i^3+6 h i j,h^2 i+4 h i^2+2 h^2 j+h^2 k+8 h i j+3 i^3+4 i^2 j+2 h j^2+2 h i k,h i^2+4 h i j+2 i^3+7 i^2 j+2 h i k+3 h j^2+4 i j^2+2 i^2 k+2 h j k,i^3+6 i^2 j+9 i j^2+3 i^2 k+2 j^3+6 i j k}]@@#&,{0,1,0,0},4]

Helm

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

Hypercube

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

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

Keller

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

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

FindSequenceFunction[DeleteMissing@seq,n]

Table[Piecewise[{{1,n==1}},(4^n)],{n,5}]

Table[GraphData[{"Keller",n},"α"],{n,5}]

Table[GraphData[{"Keller",n},"V"],{n,5}]

Table[Length@FindIndependentVertexSet[KellerGraph[n],{GraphData[{"Keller",n},"α"]},All],{n,4}]//Timing

King m×n

Table[GraphData[{"King",{m,n}},"MaximumIndependentVertexSetCount"],{n,10},{m,n}]//Column

King n×n

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

seq[[;;;;2]]

A018807

seq[[2;;;;2]]

seq2={4,79,3600,281571,32572756,5109144543,1027533353168,254977173389319,75925129079783308,26568150968269086211,10749154284380665611224,4963704194366362387891227,2588716234142991968960920692,1511548995678989691821551648635};

FindLinearRecurrence[seq2]

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

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

Knight m×n

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

Table[GraphData[{"Knight",{m,n}},"MaximumIndependentVertexSetCount"],{n,10},{m,n}]//Column

seq=Table[MaximumIndependentVertexSetCount[KnightTourGraph[2,n]],{n,50}]

seq[[1;;;;4]]

FindSequenceFunction[%,(n+3)/4]

seq[[2;;;;4]]

FindSequenceFunction[%,(n+4)/4]

seq[[3;;;;4]]

FindSequenceFunction[%,(n+1)/4]//Factor

seq[[4;;;;4]]

FindSequenceFunction[%,n/4]//Factor

Table[Piecewise[{{(1/16) (((3+n))^2),Mod[n,4]==1},{1,Mod[n,4]==2},{(1/16) (((5+n))^2),Mod[n,4]==3},{(1/256) (((4+n))^4),Mod[n,4]==0}}],{n,50}]==seq

seq=Table[MaximumIndependentVertexSetCount[KnightTourGraph[3,n]],{n,30}]

Table[{
MaximumIndependentVertexSetCount[KnightTourGraph[m,n]]
},{n,15},{m,n}]//Column

DeleteCases[Block[{m,n},{
{m,n}=GraphData[#,"NotationRules","Knight"],
GraphData[#,"MaximumIndependentVertexSetCount"],
Piecewise[{
{1,Min[m,n]==1},
{(1/16) (((3+Max[m,n]))^2),Min[m,n]==2&&Mod[Max[m,n],4]==1},
{1,Min[m,n]==2&&Mod[Max[m,n],4]==2},
{(1/16) (((5+Max[m,n]))^2),Min[m,n]==2&&Mod[Max[m,n],4]==3},
{(1/256) (((4+Max[m,n]))^4),Min[m,n]==2&&Mod[Max[m,n],4]==0},
{2 ,m==n==3||(Min[m,n]==3&&Max[m,n]==5)},
{3,(Min[m,n]==3&&Max[m,n]==4)},
{4,Min[m,n]==3&&Max[m,n]==6},
{6,m==n==4},
{3,Min[m,n]==4},
{1, Mod[m  n,2]==1},
{2, Mod[m  n,2]==0}
}]
}&/@GraphData["Knight"]],{_,x_,x_}]

DeleteCases[Flatten[Table[
{
{m,n},
MaximumIndependentVertexSetCount[KnightTourGraph[m,n]],
Piecewise[{
{1,Min[m,n]==1||(Min[m,n]==2&&Mod[Max[m,n],4]==2)},
{(1/16) (((Max[m,n]+3))^2),Min[m,n]==2&&Mod[Max[m,n],4]==1},
{(1/16) (((Max[m,n]+5))^2),Min[m,n]==2&&Mod[Max[m,n],4]==3},
{(1/256) (((Max[m,n]+4))^4),Min[m,n]==2&&Mod[Max[m,n],4]==0},
{2,m==n==3||(Min[m,n]==3&&Max[m,n]==5)},
{3,Min[m,n]==3&&Max[m,n]==4},
{4,Min[m,n]==3&&Max[m,n]==6},
{6,m==n==4},
{3,Min[m,n]==4},
{1, Mod[m  n,2]==1},
{2, Mod[m  n,2]==0}
}]},{n,20},{m,20}],1],{_,x_,x_}]//Timing

Knight n×n

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

Table[GraphData[{"Knight",{n,n}},"MaximumIndependentVertexSetCount"],{n,20}]

Ladder

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

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

LadderRung

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

FindSequenceFunction[seq,n]

MengerSponge

Inferred for n == 3:

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

Table[With[{gn={"MengerSponge",n}},HighlightGraph[Annotate[GraphData[gn,"Graph","3D"],VertexSize->{"Scaled",.03}],GraphData[gn,"MaximumIndependentVertexSets"][[1]]]],{n,2}]

Table[GraphData[{"MengerSponge",n},"MaximumIndependentVertexSets"],{n,2}]//Column

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

Position[VertexDegree[GraphData[{"MengerSponge",1}]],2]//Flatten

VertexDegree[GraphData[{"MengerSponge",2}]][[GraphData[{"MengerSponge",2},"MaximumIndependentVertexSets"][[1]]]]

Union[%]

GraphData[{"MengerSponge",2},"VertexDegreePolynomial"][x]

Position[VertexDegree[GraphData[{"MengerSponge",2}]],3|5|6]//Flatten

Position[VertexDegree[GraphData[{"MengerSponge",2}]],3]//Flatten

Do[Print[{gn={"MengerSponge",n},FindAllMaximumIndependentVertexSets[GraphData[gn]]//Timing}],{n,2}]

Do[Print[{gn={"MengerSponge",n},MaximumIndependentVertexSetCount[GraphData[gn]]//Timing}],{n,3}]

MoebiusLadder

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

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

Mycielski

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

seq=Table[GraphData[{"Mycielski",n},"MaximumIndependentVertexSetCount"],{n,8}]

Odd

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

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

Pan

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

Path

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

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

Prism

A266722

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

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

seq=Table[1+(((-1))^(1+n)) (-1+n)+n,{n,3,25}]

Queen n×n

A000170

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

Rook m×n

A008279

seq=Table[GraphData[{"Rook",{m,n}},"MaximumIndependentVertexSetCount"],{n,10},{m,n}]//Column

Table[FactorialPower[n,k],{n,10},{k,n}]//Column

Rook n×n

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

RookComplement n×n

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

FindSequenceFunction[Rest@seq,n-1]

SierpinskiCarpet

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

Do[Print[{gn={"SierpinskiCarpet",n},MaximumIndependentVertexSetCount[SierpinskiCarpetGraph[n]]//Timing}],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"MaximumIndependentVertexSetCount"],{n,5}]

SierpinskiTetrahedron

A360131

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

Table[GraphData[{"SierpinskiTetrahedron",n},"α"],{n,6}]

Table[GraphData[{"SierpinskiTetrahedron",n},"V"],{n,6}]

Do[Print[{gn={"SierpinskiTetrahedron",n},MaximumIndependentVertexSetCount[SierpinskiTetrahedronGraph[n]]//Timing}],{n,6}]

Star

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

seq=Table[GraphData[{"Star",n},"MaximumIndependentVertexSetCount"],{n,20}]

Sun

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

Sunlet

A000032

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

FindSequenceFunction[seq,n-2]

LucasL[Range[3,20]]

Tetrahedral

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

seq[[;;;;2]]

FindSequenceFunction[{30,840,1814400},n]

TorusGrid n×n

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

Table[GraphData[{"TorusGrid",{n,n}},"IndependenceNumber"],{n,3,20}]

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

Simplify[(n+Mod[n-1,2]-1)n/2]

Do[Print[{gn={"TorusGrid",{n,n}},MaximumIndependentVertexSetCount[GraphData[gn]]//Timing}],{n,3,20}]

Table[GraphData[{"TorusGrid",{n,n}},"MaximumIndependentVertexSets"]/.l_List:>Length[l],{n,3,20}]//Column

Do[Print[{gn={"TorusGrid",{n,n}},FindIndependentVertexSet[GraphData[gn],{(n-Mod[n,2])n/2}]//Timing}],{n,15,19,2}]

Do[Print[{gn={"TorusGrid",{n,n}},FindIndependentVertexSet[GraphData[gn],{(n-Mod[n,2])n/2},All]//Timing}],{n,3,10}]

Transposition

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

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

Triangular

Cell[TextData[ButtonBox["A133221",
 BaseStyle->"Hyperlink",
 ButtonData->{
   URL["https://oeis.org/A133221"], None},
 ButtonNote->"https://oeis.org/A133221"]], "Text"]

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

Table[2n!!,{n,2,10}]

Table[If[Mod[n,2]==0,(n-1)!!,n!!],{n,2,20}]

Table[If[Mod[n,2]==1,(n-2)!!,(n-1)!!],{n,0,20}]

Table[(n-1-Mod[n,2])!!,{n,0,20}]

FullSimplify[(n-1-(1-(((-1))^n))/2)]

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

TriangularGrid

A297557

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

seq=BFileSequence[297557]

gf=FindGeneratingFunction[seq,x]

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

Table[(1/3) (55-52 Cos[((2 n π)/3)]),{n,8,24}]

Do[Print[{{"TriangularGrid",n},MaximumIndependentVertexSetCount[TriangularGridGraph[n]]//Timing}],{n,0,24}]

TriangularHoneycombAcuteKnight

A297537

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

seq=Table[Piecewise[{
{((CatalanNumber[n/3+1])^3),Mod[n,3]==0},
{{1,9,196,6084,219024,8450649,338265664,13840346025,574510941225,24093764931600}[[(n+2)/3]],Mod[n,3]==1},
{1,Mod[n,3]==2}
}],{n,30}]

A244506

seq[[;;;;3]]

FindSequenceFunction[Rest@%,n]

seq[[2;;;;3]]

A033536

seq[[3;;;;3]]

Table[CatalanNumber@n^3,{n,10}]

CatalanNumber[Range[0,20]]^3

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

A299709

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

TriangularHoneycombQueen

A289893

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

seq=BFileSequence[289893]

A002047

seq[[;;;;3]]

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

seq[[2;;;;3]]

FindGeneratingFunction[seq[[2;;;;3]],x]//Head//Timing

seq[[3;;;;3]]

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

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

TriangularHoneycombRook

A000142

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

FindSequenceFunction[DeleteMissing@seq,n]

Web

A297439

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

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

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

FullSimplify[ ((2^((1/2) (-5+n)))4 (Sqrt[2]) (1+(((-1))^n))-3 (2^((1/2) (-5+n)))(-1+(((-1))^n)) n),n∈Integers]

FullSimplify[ {(2^((1/2) (-5+n)))4 (Sqrt[2]) (1+(((-1))^n)),3 (2^((1/2) (-5+n)))(-1+(((-1))^n)) n},n∈Integers]

FullSimplify[(2^(n/2))(1+(((-1))^n)-3 (2^(-5/2)) (-1+(((-1))^n)) n)]

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

FullSimplify[(2^(n/2))(1+(((-1))^n)-3 (2^(-5/2)) (-1+(((-1))^n)) n),Mod[n,2]==#]&/@{0,1}

Table[If[Mod[n,2]==0,(2^(n/2+1)),3 (2^((n-3)/2))n],{n,2,40}]

FindLinearRecurrence[seq]

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

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

Wheel

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

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

WhiteBishop n×n

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

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

Zebra n×n

Table[GraphData[{"Zebra",{n,n}},"MaximumIndependentVertexSetCount"],{n,20}]

Bipartite

b=GraphData[{"Connected","Bipartite"},2;;5]

Connected bipartite graphs may have 1, 2, or more maximum independent vertex sets

(GraphData[#,"MaximumIndependentVertexSets"]&/@b)//Column

Tally[Sort[GraphData[#,"MaximumIndependentVertexSetCount"]&/@GraphData[{"Connected","Bipartite"},2;;5]]]

Tally[Sort[GraphData[#,"MaximumIndependentVertexSetCount"]&/@GraphData[{"Connected","Bipartite"},2;;10]]]

Connected bipartite graphs may have 2 or more maximal independent vertex sets

(GraphData[#,"MaximalIndependentVertexSets"]&/@b)//Column

Tally[Sort[GraphData[#,"MaximalIndependentVertexSetCount"]&/@GraphData[{"Connected","Bipartite"},2;;10]]]

Check graphs with alpha = V/2

TextGrid[
Cases[GraphData[#,{"#","VertexCount","IndependenceNumber","MaximumIndependentVertexSetCount"}]&/@GraphData[{"Connected","Bipartite"},2;;6],{_,n_,alpha_,_}/;n==2alpha],
Dividers->All]

GraphData["EGraph",{"V","IndependenceNumber"}]

HighlightGraph[GraphData["EGraph","Graph","Labeled"],#]&/@GraphData["EGraph","MaximumIndependentVertexSets"]

2Banner+P2

Select[GraphData["Bipartite"],GraphData[#,"MaximumIndependentVertexSetCount"]===2&]

HighlightGraph[g=GraphData[gn={7,77}],#]&/@GraphData[gn,"MaximumIndependentVertexSets"]

Sort[Sort/@IGraphM`IGLargestCliques[GraphComplement[g]]]

FindAllMaximumIndependentVertexSets[GraphData[gn],Debug->True]

Algorithm comparison

(Subscript[Q, 4])

(i1=FindAllMaximumIndependentVertexSets[GraphData["Q4"],All,Method->"FindClique"])//Length//Timing

(i2=FindAllMaximumIndependentVertexSets[GraphData["Q4"],Method->"FindIndependentVertexSet"])//Length//Timing

(i3=FindAllMaximumIndependentVertexSets[GraphData["Q4"],Method->"IndependentVertexSetQ"])//Length//Timing

i1==i2==i3

(Subscript[Q, 5])

(i1=FindAllMaximumIndependentVertexSets[GraphData["Q5"],All,Method->"FindClique"])//Length//Timing

(i2=FindAllMaximumIndependentVertexSets[GraphData["Q5"],Method->"FindIndependentVertexSet"])//Length//Timing

(i3=FindAllMaximumIndependentVertexSets[GraphData["Q5"],Method->"IndependentVertexSetQ"])//Length//Timing

i1==i2

Graphs on <=20 nodes

Monitor[Select[GraphData[;;20],FindAllMaximumIndependentVertexSets[GraphData[g=#],Method->"FindIndependentVertexSet"]=!=FindAllMaximumIndependentVertexSets[GraphData[#],Method->"IndependentVertexSetQ"]&],g]//Timing

Monitor[Select[GraphData[;;20],FindAllMaximumIndependentVertexSets[GraphData[g=#],Method->"FindIndependentVertexSet"]=!=FindAllMaximumIndependentVertexSets[GraphData[#],Method->"FindClique"]&],g]//Timing

Difference between -mal and -mum

Cases[{#,AllMaximalIndependentVertexSets[GraphData[#]],AllMaximumIndependentVertexSets[GraphData[#]]}&/@GraphData[;;5],{_,x_,x_}]

DeleteCases[{#,AllMaximalIndependentVertexSets[GraphData[#]],AllMaximumIndependentVertexSets[GraphData[#]]}&/@GraphData[;;5],{_,x_,x_}]

AllMaximalIndependentVertexSets[GraphData["ThreeP3"]]

AllMaximumIndependentVertexSets[GraphData["ThreeP3"]]

check={"ThreeP3",{"Bishop",{3,3}},{"BlackBishop",{3,6}},{"Bishop",{2,5}},{"WhiteBishop",{3,7}},{"BlackBishop",{3,7}},{"Bishop",{2,6}},{"Bishop",{3,4}},{"BlackBishop",{3,8}},{"BlackBishop",{4,6}},{"WhiteBishop",{5,5}},{"BlackBishop",{5,5}},{"WhiteBishop",{3,9}},{"Bishop",{2,7}},{"BlackBishop",{3,9}},{"BlackBishop",{4,7}},{"Bishop",{3,5}},{"BlackBishop",{3,10}},{"BlackBishop",{5,6}},{"Bishop",{2,8}},{"Bishop",{4,4}},{"BlackBishop",{4,8}},{"ZeroTwoNonbipartite",{5,4}},{"WhiteBishop",{5,7}},{"Bishop",{2,9}},{"Bishop",{3,6}},{"BlackBishop",{4,9}},{"BlackBishop",{5,7}},{"BlackBishop",{6,6}},{"Bishop",{4,5}},{"BlackBishop",{4,10}},{"BlackBishop",{5,8}},{"ZeroTwoNonbipartite",{6,4}},{"Bishop",{3,7}},{"BlackBishop",{6,7}},{"WhiteBishop",{5,9}},{"BlackBishop",{5,9}},{"ZeroTwoBipartite",{5,2}},{"ZeroTwoNonbipartite",{7,4}},{"ZeroTwoNonbipartite",{7,5}},{"ZeroTwoNonbipartite",{7,6}},{"ZeroTwoNonbipartite",{7,10}}};

Select[check,GraphData[#,"MaximalIndependentVertexSets"]=!=AllMaximalIndependentVertexSets[GraphData[#]]&]

Select[check,GraphData[#,"MaximumIndependentVertexSets"]=!=AllMaximumIndependentVertexSets[GraphData[#]]&]

MaximumIndependentVertexSets == MinimumVertexCover

If a graph is bipartite, connected, and symmetric on >= 2 nodes

DeleteCases[GraphData[#,{"#","MaximumIndependentVertexSets","MinimumVertexCovers"}]&/@GraphData[{"Bipartite","Connected","Symmetric"}],{_,x_,x_}]

Not necessarily true for these:

Complement[added,GraphData[{"Bipartite","Connected","VertexTransitive"}]]

Complement[added,GraphData[{"Bipartite","Connected","Symmetric"}]]

Same as α==n/2 && |MIVS| = 2

DeleteCases[GraphData[#,{"#","MaximumIndependentVertexSets","MinimumVertexCovers"}]&/@Select[GraphData["Bipartite"],GraphData[#,"IndependenceNumber"]==GraphData[#,"V"]/2&&GraphData[#,"MaximumIndependentVertexSetCount"]==2&],{_,x_,x_}]

Counterexamples |V| even

bad=DeleteCases[GraphData[#,{"#","MaximumIndependentVertexSets","MinimumVertexCovers"}]&/@Select[SortBy[GraphData[{"Connected","Bipartite"}],GraphData[#,"V"]&],Mod[GraphData[#,"V"],2]==0&],{_,x_,x_}]

GraphData[bad[[1,1]],"Graph","Labeled"]

GraphData[bad[[1,1]],"MaximumIndependentVertexSets"]

Counterexamples for |MIVS|==2

bad=DeleteCases[GraphData[#,{"#","MaximumIndependentVertexSets","MinimumVertexCovers"}]&/@Select[
SortBy[GraphData[{"Connected","Bipartite"}],GraphData[#,"V"]&],GraphData[#,"MaximumIndependentVertexSetCount"]==2&],{_,x_,x_}]

GraphData[bad[[1,1]],"Graph","Labeled"]

GraphData[bad[[1,1]],"MaximumIndependentVertexSets"]

Counterexamples for |MIVS|==2 and |V| even

bad=DeleteCases[GraphData[#,{"#","MaximumIndependentVertexSets","MinimumVertexCovers"}]&/@Select[SortBy[GraphData[{"Connected","Bipartite"}],GraphData[#,"V"]&],Mod[GraphData[#,"V"],2]==0&&GraphData[#,"MaximumIndependentVertexSetCount"]==2&],{_,x_,x_}]

GraphData[bad[[1,1]],"Graph","Labeled"]

GraphData[bad[[1,1]],"MaximumIndependentVertexSets"]