Vertex Cover

Author

Eric W. Weisstein
February 18, 2014

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

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

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

Figure

vc[g_Graph]:=Module[{n=V[g]},
Graphics[showGraph[g,
PlotStyles->{AbsolutePointSize[7]},
VertexColors->(ReplacePart[Table[Black,{n}],Red,List/@MinimumVertexCover[g]])],PlotRange->All]
]

Show[GraphicsArray[vc/@{Wheel[8],UtilityGraph,PetersenGraph,FruchtGraph}]]

Algorithm Comparison

?FindAllVertexCovers

(Subscript[Q, 4])

Length[v1=FindAllVertexCovers[GraphData["Q4"],Method->{"VertexCoverQ",All}]]//Timing

Length[v2=FindAllVertexCovers[GraphData["Q4"],Method->{"VertexCoverQ","KSubsets"}]]//Timing

Length[v3=FindAllVertexCovers[GraphData["Q4"],Method->"FindIndependentVertexSet"]]//Timing

v1==v2==v3

FindAllVertexCovers[GraphData["Q4"],Method->"FindVertexCover"]

Relation to independent vertex sets

GraphData["AntennaGraph",{"LabeledGraph","V","M"}]

ies=FindAllIndependentVertexSets[GraphData["AntennaGraph"]]

c1=Sort[Complement[Range[6],#]&/@ies]

c2=FindAllVertexCovers[GraphData["AntennaGraph"]]

c1==c2

Select[GraphData[;;7],Function[g,FindAllVertexCovers[GraphData[g]]=!=Sort[Complement[Range[GraphData[g,"V"]],#]&/@FindAllIndependentVertexSets[GraphData[g]]]]]//Timing

Families

Andrasfai

l=DeleteCases[Quiet[Table[{n,GraphData[{"Andrasfai",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Antiprism

l=DeleteCases[Quiet[Table[{n,GraphData[{"Antiprism",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-2]//FullSimplify

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

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

-1-2 #1-((#1)^2)+((#1)^3)&@x//TraditionalForm

FindGeneratingFunction[seq,x]//FullSimplify

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

Bishop

https://oeis.org/A201862

l=DeleteCases[Quiet[Table[{n,GraphData[{"Bishop",{n,n}},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

BlackBishop

l=DeleteCases[Quiet[Table[{n,GraphData[{"BlackBishop",{n,n}},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Book

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

FindSequenceFunction[seq,n]//FullSimplify

Bruhat

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

CocktailParty

l=DeleteCases[Quiet[Table[{n,GraphData[{"CocktailParty",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Complete

l=DeleteCases[Quiet[Table[{n,GraphData[{"Complete",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]

CompleteBipartite

l=DeleteCases[Quiet[Table[{n,GraphData[{"CompleteBipartite",{n,n}},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]

CompleteTripartite

l=DeleteCases[Quiet[Table[{n,GraphData[{"CompleteTripartite",{n,n,n}},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]

CrossedPrism

l=DeleteCases[Quiet[Table[{n,GraphData[{"CrossedPrism",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-1]//FullSimplify

gf=x^4FindGeneratingFunction[seq,x]

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

CubeConnectedCycle

l=DeleteCases[Quiet[Table[{n,GraphData[{"CubeConnectedCycle",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

Cycle

l=DeleteCases[Quiet[Table[{n,GraphData[{"Cycle",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-2]

Table[LucasL[n],{n,20}]

FindSequenceFunction[%,n]

Empty

l=DeleteCases[Quiet[Table[{n,GraphData[{"Empty",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]

FoldedCube

l=DeleteCases[Quiet[Table[{n,GraphData[{"FoldedCube",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

Gear

l=DeleteCases[Quiet[Table[{n,GraphData[{"Gear",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

gf=x^3FindGeneratingFunction[seq,x]

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

(1/2) (3-(Sqrt[5]))//N

1/(GoldenRatio+1)//N

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

Grid nxn

https://oeis.org/A006506

l=DeleteCases[Quiet[Table[{n,GraphData[{"Grid",{n,n}},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-1]//FullSimplify

Grid nxnxn

l=DeleteCases[Quiet[Table[{n,GraphData[{"Grid",{n,n,n}},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

HalvedCube

l=DeleteCases[Quiet[Table[{n,GraphData[{"HalvedCube",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

Hanoi

l=DeleteCases[Quiet[Table[{n,GraphData[{"Hanoi",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

Helm

l=DeleteCases[Quiet[Table[{n,GraphData[{"Helm",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-2]//FullSimplify

gf=x^3FindGeneratingFunction[seq,x]

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

Hypercube

https://oeis.org/A027624

l=DeleteCases[Quiet[Table[{n,GraphData[{"Hypercube",n},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

King

Possibly https://oeis.org/A063443

l=DeleteCases[Quiet[Table[{n,GraphData[{"King",{n,n}},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Knight

https://oeis.org/A141243

l=DeleteCases[Quiet[Table[{n,GraphData[{"Knight",{n,n}},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Ladder

l=DeleteCases[Quiet[Table[{n,GraphData[{"Ladder",n},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

gf=FindGeneratingFunction[seq,x]

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

LadderRung

l=DeleteCases[Quiet[Table[{n,GraphData[{"LadderRung",n},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]

Lattice

https://oeis.org/A002720

l=DeleteCases[Quiet[Table[{n,GraphData[{"Lattice",{n,n}},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Table[n!*LaguerreL[n,-1],{n,7}]

MoebiusLadder

https://oeis.org/A182143

l=DeleteCases[Quiet[Table[{n,GraphData[{"MoebiusLadder",n},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

gf=x^3FindGeneratingFunction[seq,x]

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

Mycielski

l=DeleteCases[Quiet[Table[{n,GraphData[{"Mycielski",n},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Odd

l=DeleteCases[Quiet[Table[{n,GraphData[{"Odd",n},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Pan

l=DeleteCases[Quiet[Table[{n,GraphData[{"Pan",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-2]

Table[Fibonacci[n+1]+LucasL[n],{n,3,20}]

Path

l=DeleteCases[Quiet[Table[{n,GraphData[{"Path",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]

Table[Fibonacci[n+2],{n,20}]

Prism

https://oeis.org/A051927

l=DeleteCases[Quiet[Table[{n,GraphData[{"Prism",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-2]//FullSimplify

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

-1-2 #1-((#1)^2)+((#1)^3)&@x//TraditionalForm

FindGeneratingFunction[seq,x]//FullSimplify

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

Queen

l=DeleteCases[Quiet[Table[{n,GraphData[{"Queen",{n,n}},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

SierpinskiCarpet

l=DeleteCases[Quiet[Table[{n,GraphData[{"SierpinskiCarpet",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

SierpinskiSieve

l=DeleteCases[Quiet[Table[{n,GraphData[{"SierpinskiSieve",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

Star

l=DeleteCases[Quiet[Table[{n,GraphData[{"Star",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Sun

l=DeleteCases[Quiet[Table[{n,GraphData[{"Sun",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-2]//FullSimplify

Sunlet

l=DeleteCases[Quiet[Table[{n,GraphData[{"Sunlet",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-2]//FullSimplify

TorusGrid

l=DeleteCases[Quiet[Table[{n,GraphData[{"TorusGrid",{n,n}},"VertexCoverCount"]},{n,10}]],{_,_GraphData|_Missing}]

Triangular

l=DeleteCases[Quiet[Table[{n,GraphData[{"Triangular",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify

Web

l=DeleteCases[Quiet[Table[{n,GraphData[{"Web",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-2]

Wheel

l=DeleteCases[Quiet[Table[{n,GraphData[{"Wheel",n},"VertexCoverCount"]},{n,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n-3]

Table[LucasL[n-1]+1,{n,4,20}]

WhiteBishop

l=DeleteCases[Quiet[Table[{n,GraphData[{"WhiteBishop",{n,n}},"VertexCoverCount"]},{n,0,30}]],{_,_GraphData|_Missing}]

seq=l[[All,2]]

FindSequenceFunction[seq,n]//FullSimplify