Independence Number

Author

Eric W. Weisstein
December 8, 2023

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

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

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

Counts

Tally[Sort[#]]&/@(values=Table[IndependenceNumber/@Graphs[n],{n,8}])//Column

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

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Get/@FileNames[]))//Column

A263341

Flatten[tallies]

A000088

Total/@tallies

Length/@tallies

Not in OEIS:

Total/@values

Missing

DateString[]

Grid[missing=Cases[Sort[GraphData[#,{"V","IndependenceNumber","#"}]&/@GraphData[All]],{v_,_Missing,g_}:>{v,g}],Alignment->Left,Dividers->All]

Length[missing]

Export["/Users/eww/Documents/Mathematica/Paclets/GraphData/Data/ForPratt/IndependenceNumber.tsv",{GraphNameToPrattName[#2],#1,GraphData[#2,"M"]}&@@@missing]

Properties

"Bipartite","Connected"

No pattern?:

Grid[GraphData[#,{"#","V","α"}]&/@GraphData[{"Bipartite","Connected"},;;5]]

"Bipartite","Connected","Nonempty","VertexTransitive"

α == n/2

Grid[GraphData[#,{"#","V","α"}]&/@GraphData[{"Bipartite","Connected","Nonempty","VertexTransitive"},;;10]]

Relationships

CliqueNumber of GraphComplement

DeleteCases[{#,IndependenceNumber[GraphData[#]],CliqueNumber[GraphComplement[GraphData[#]]]}&/@GraphData[;;10],{_,x_,x_}]

Parametrized families

<<MathWorld`Graphs`

GraphDataCountTable["IndependenceNumber",{"Antelope"->286069,"CubeConnectedCycle"->291938,"DiagonalIntersection"->300569,"FibonacciCube"->173173,"Fiveleaper"->301758,"FoldedCube"->058622,"Goldberg"->047355,"Grid"->000982,{"Grid",3}->036486,"HalvedCube"->005864,"HexagonalGrid"->033428,"Knight"->030978,"MengerSponge"->307691,"Mycielski"->266550,"Odd"->001791,"Pasechnik"->004767,"SierpinskiCarpet"->013731,"SierpinskiTetrahedron"->283070,"TorusGrid"->093353,"TriangulaGrid"->239438,"Web"->032766}]

AlternatingGroup

Looks similar to A208232

Maximum order of a subgroup of the symmetric group of degree n that contains no 2-cycle and no 3-cycle.

1, 1, 1, 4, 20, 120, 168, 1344, 1512, 1920, 7920, 95040, 9504

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

Andrasfai

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

Table[n,{n,3,10}]

Antelope n×n

A286069

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

Join[{1,4,9,16,21,24,25,36,48,60,72,84,92,98,113,132,153,168,185},LinearRecurrence[{2,0,-2,1},{1,2,5,8},{20}]]==seq

Antiprism

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

A004523

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

FindSequenceFunction[l,n+2]//FullSimplify

Table[Floor[2n/3],{n,3,20}]

Apollonian

A000244

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

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

Barbell

A007395

seq=Table[GraphData[{"Barbell",n},"IndependenceNumber"],{n,3,10}]

Bishop n×n

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

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

BlackBishop n×n

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

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

Boook

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

Bruhat

A001710

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

(seq=Table[Length[FindIndependentVertexSet[BruhatGraph[n]][[1]]],{n,7}])//Timing

FindSequenceFunction[seq,n]

Table[n!/2,{n,7}]

Table[GroupOrder[System`AlternatingGroup[n]],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"IndependenceNumber"],{n,10}]

Complete

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

IndependenceNumber[CompleteGraph[#]]&/@Range[12]

CompleteBipartite m×n

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

CompleteBipartite n×n

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

IndependenceNumber[CompleteGraph[#,#]]&/@Range[12]

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

IndependenceNumber[CompleteGraph[#,#,#]]&/@Range[10]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",n},"IndependenceNumber"],{n,4,20,2}]

Table[n,{n,4,20,2}]

Crown

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

CubeConnectedCycle

A291938

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

Table[FindIndependentVertexSet[CubeConnectedCycleGraph[n]]//Flatten//Length,{n,3,4}]//Timing

FindSequenceFunction[seq,n-2]//FullSimplify

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

Table[Piecewise[{{(2^(n-1)) n ,Mod[n,2]==0},{(2^(n-1))  (n-1),Mod[n,2]==1}}],{n,3,8}]

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

FullSimplify[(2^n) n Piecewise[{{1/2,Mod[n,2]==0},{((n-1)/(2n)),Mod[n,2]==1}}]]

seq=Table[(2^(n-1))(n-Mod[n,2]),{n,30}]

FindLinearRecurrence[seq]

LinearRecurrence[{2,4,-8},{0,4,8},20]

gf=x FindGeneratingFunction[seq,x]

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

Cycle

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

A004526

Table[GraphData[{"Cycle",n},"IndependenceNumber"],{n,3,12}]

IndependenceNumber[Cycle[#]]&/@Range[3,12]

Table[Floor[n/2],{n,3,16}]

DiagonalIntersection

A300569

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

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

FindLinearRecurrence[DeleteMissing@seq]//Head

FindLinearRecurrence[Rest@DeleteMissing@seq]//Head

FindGeneratingFunction[seq,x]//Head

DorogovtsevGoltsevMendes

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

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

Empty

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

Table[GraphData[{"Empty",n},"IndependenceNumber"],{n,30}]

FibonacciCube

A173173

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

Table[Ceiling[Fibonacci[n]/2],{n,0,20}]

Ceiling[Fibonacci[Range[0,20]]/2]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{1,1,1,-1,-1},{1,2,3,4,7},20]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

gf=x FindGeneratingFunction[seq,x]

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

Fiveleaper n×n

A301758

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

Join[{1,4,9,16,21,22},Table[(3-(-1)^n+2 (n-1)(n+1))/4,{n,7,20}]]==seq

FoldedCube

A058622

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

Table[2^(n-2)-((1-(-1)^n)/4)*Binomial[n-1,(n-1)/2],{n,2,20}]

Gear

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

Goldberg

A047355

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

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

Grid m×n

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

DeleteCases[Flatten[Table[{{m,n},GraphData[{"Grid",{m,n}},"IndependenceNumber"],Ceiling[m n/2]},{n,2,10},{m,n}],1],{_,x_,x_}]

Grid n×n

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

A000982

Table[GraphData[{"Grid",{n,n}},"IndependenceNumber"],{n,2,10}]

FullSimplify[FindSequenceFunction[%,n-1],n∈Integers]

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

Grid n×n×n

A036486

Table[GraphData[{"Grid",{n,n,n}},"IndependenceNumber"],{n,2,10}]

FullSimplify[FindSequenceFunction[%,n-1],n∈Integers]

Table[Ceiling[n^3/2],{n,10}]

HalvedCube

A005864 (conjectured)

The coding-theoretic function A(n,4).

Table[GraphData[{"HalvedCube",n},"IndependenceNumber"],{n,1,10}]

Hanoi

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

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

Helm

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

Hypercube

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

A000079

IndependenceNumber[Hypercube[#]]&/@Range[7]

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

Keller

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

A258935

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

Table[Piecewise[{{4,n==1},{5,n==2}},2^n],{n,10}]

King m×n

King n×n

A008794

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

Table[Floor[(n+1)/2]^2,{n,2,10}]

Knight m×n

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

Knight n×n

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

A030978

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

n^2/2 if n even > 2, (n^2+1)/2 if n odd > 1.

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

SeriesCoefficient[x*(2*x^5-4*x^4+3*x^2-2*x-1)/((x-1)^3*(x+1)),{x,0,n}]

Ladder

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

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

LadderRung

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

MengerSponge

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

MoebiusLadder

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

A109613

Table[GraphData[{"MoebiusLadder",n},"IndependenceNumber"],{n,3,25}]

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

Mycielski

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

A266550

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

Table[(3*2^(n-2)-2)/2,{n,11}]

Series[1+x^2(1-x+x^2)/((1-x)*(1-2*x)),{x,0,10}]

FullSimplify[1+x^2(1-x+x^2)/((1-x)*(1-2*x))]

SeriesCoefficient[1+x^2(1-x+x^2)/((1-x)*(1-2*x)),{x,0,n}]

Table[Piecewise[{{-1+3 (2^(-3+n)),n>2}},1],{n,35}]

Odd

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

Almost A001791

1, 4, 15, 56, 210, 792, 3003,

Binomial coefficients C(2n,n-1).

Table[GraphData[{"Odd",n},"IndependenceNumber"],{n,7}]

Table[Binomial[2n-2,n-2],{n,12}]

Pan

Table[GraphData[{"Pan",n},"IndependenceNumber"],{n,3,12}]

Table[1+Floor[n/2],{n,3,15}]

Path

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

A004526

IndependenceNumber[Path[#]]&/@Range[12]

Table[Ceiling[n/2],{n,12}]

Table[Floor[(n+1)/2],{n,12}]

Prism

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

A052928

Table[GraphData[{"Prism",n},"IndependenceNumber"],{n,3,25}]

Table[2Floor[n/2],{n,3,10}]

Queen n×n

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

Rook n×n

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

RookComplement n×n

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

Do[Print[{n,Length@FindIndependentVertexSet[System`GraphComplement[RookGraph[n,n]]][[1]]//Timing}],{n,10}]

SierpinskiCarpet

Possibly A013731

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

seq={4,32,256,2048,16384};

seq=Table[(2^(3n+2)),{n,0,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{8},{4},20]

2^(3Range[0,20]+2)

gf=FindGeneratingFunction[seq,x]

CoefficientList[Series[-(4/(-1+8 x)),{x,0,20}],x]

SierpinskiSieve

Need another term to distinguish from existing sequences

Table[GraphData[{"SierpinskiSieve",n},"IndependenceNumber"],{n,5}]

Do[Print[{n,Length[Flatten[FindMaximumIndependentVertexSet[SierpinskiSieveGraph[n],Method->"FindIndependentVertexSet"]]]//Timing}],{n,6}]

SierpinskiTetrahedron

Essentially A283070 (with 1 prepended)

Computed up to n==6; inferred for n==6

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

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]//FullSimplify

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

Star

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

A028310

Table[GraphData[{"Star",n},"IndependenceNumber"],{n,12}]

IndependenceNumber[Star[#]]&/@Range[12]

Table[Piecewise[{{1,n==1}},n-1],{n,12}]

Sun

Table[GraphData[{"Sun",n},"IndependenceNumber"],{n,3,10}]

Sunlet

Table[GraphData[{"Sunlet",n},"IndependenceNumber"],{n,3,10}]

Tetrahedral

Possibly A001839

Table[GraphData[{"Tetrahedral",n},"IndependenceNumber"],{n,6,10}]

seq={4,7,8,12,13,17,20};

TorusGrid n×n

A093353

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

Table[n Floor[n/2],{n,3,20}]==%

Triangular

A004526

Table[GraphData[{"Triangular",n},"IndependenceNumber"],{n,2,12}]

Table[Floor[n/2],{n,2,12}]

TriangularGrid

A239438

Table[GraphData[{"TriangularGrid",n},"IndependenceNumber"],{n,0,10}]

Table[1/18 (Piecewise[{{28,n==2||n==4}},10]+3 n (3+n)+8 Cos[(2 n Pi)/3]),{n,0,20}]

TriangularHoneycombAcuteKnight

A287195

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

FindLinearRecurrence[seq]

LinearRecurrence[{1,0,2,-2,0,-1,1},{1,3,3,5,9,9,12},50]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

Table[(1/18) ((n+3) (3n+2)-2 (n+3) Cos[((2 n π)/3)]-2 (Sqrt[3]) (n+1) Sin[((2 n π)/3)]),{n,50}]

seq=Table[(1/18) ((n+3) (3n+2)-2 (n+3) Cos[((2 n π)/3)]-2 (Sqrt[3]) (n+1) Sin[((2 n π)/3)]),{n,1,50,3}]

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

Table[(1/18) ((n+3) (3n+2)-2 (n+3) Cos[((2 n π)/3)]-2 (Sqrt[3]) (n+1) Sin[((2 n π)/3)]),{n,2,50,3}]

FindSequenceFunction[%,(n-2)/3+1]//FullSimplify

seq=Table[(1/18) ((n+3) (3n+2)-2 (n+3) Cos[((2 n π)/3)]-2 (Sqrt[3]) (n+1) Sin[((2 n π)/3)]),{n,3,50,3}]

FindSequenceFunction[seq,n/3]//FullSimplify

Table[Piecewise[{{n(n+3),Mod[n,3]==0},{(n+1) (n+2),Mod[n,3]==1},{(n+1) (n+4),Mod[n,3]==2}}]/6,{n,50}]

TriangularHoneycombBishop

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

Do[Print[{gn=GraphData[{"TriangularHoneycombBishop",n},"#"],MyFindIndependentVertexSet[GraphData[gn],Method->{"LinearOptimization","Vector","MOSEK"}]//Timing}],{n,2,17}]

TriangularHoneycombObtuseKnight

A251532

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"IndependenceNumber"],{n,10}]

Do[Print[{n,{Length[ivs=FindIndependentVertexSet[TriangularHoneycombObtuseKnightGraph[n]][[1]]],ivs}//Timing}],{n,21}]

seq={1,3,6,7,7,9,15,18,21,21,27,31,36,42,42,47,54,62,70,70,77,85,95,105};

Table[FindLinearRecurrence[Drop[seq,k]],{k,0,3}]//Column

gf=x FindGeneratingFunction[seq,x]

TriangularHoneycombQueen

A004396

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

Table[Floor[(2 n+1)/3],{n,15}]

Do[Print[{gn={"TriangularHoneycombQueen",n},MyFindIndependentVertexSet[GraphData[gn],Method->{"LinearOptimization","Vector","MOSEK"}]//Timing}],{n,2,17}]

TriangularHoneycombRook

Table[GraphData[{"TriangularHoneycombRook",n},"IndependenceNumber"],{n,10}]

Web

A032766

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

FullSimplify[FindSequenceFunction[%,n-2],n∈Integers&&n>0]

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

Wheel

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

IndependenceNumber[Wheel[#]]&/@Range[3,12]

Table[GraphData[{"Wheel",n},"IndependenceNumber"],{n,4,12}]

Table[Ceiling[n/2]-1,{n,4,12}]

Table[Floor[(n-1)/2],{n,4,12}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"IndependenceNumber"],{n,4,10}]