Well-Covered Graph

Author

Eric W. Weisstein
June 10, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Well-CoveredGraph.nb.

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

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

Counts

Connected

A222625

Table[Total[Boole[WellCoveredGraphQ/@ConnectedGraphs[n]]],{n,7}]//Timing

Length/@Table[GraphData[{"Connected","WellCovered"},n],{n,7}]

Table[Total[Boole[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","WellCovered","WellCovered_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[ConnectedGraphIndices[n]]]]],{n,10}]

Table[Total[Boole[Equal@@@Transpose[Get[FileNameJoin[{$GraphDataDirectory,"Nodes",#,#<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[ConnectedGraphIndices[n]]]&/@{"MaximalIndependentVertexSetCount","MaximumIndependentVertexSetCount"}]]],{n,10}]//Timing

Disconnected

A287025

Table[Total[Boole[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","WellCovered","WellCovered_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[DisconnectedGraphIndices[n]]]]],{n,9}]

Table[Total[Boole[Equal@@@Transpose[Get[FileNameJoin[{$GraphDataDirectory,"Nodes",#,#<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[DisconnectedGraphIndices[n]]]&/@{"MaximalIndependentVertexSetCount","MaximumIndependentVertexSetCount"}]]],{n,10}]//Timing

Length/@Table[GraphData[{"Disconnected","WellCovered"},n],{n,7}]

{1,2,3,7,14,46,164,996,10195,208168}-{1,1,1,3,6,27,108,788,9035,196928}

All

A222626

Table[Total[Boole[WellCoveredGraphQ/@Graphs[n]]],{n,7}]//Timing

Length/@Table[GraphData["WellCovered",n],{n,7}]

Total[Boole[Get[#]]]&/@FileNames["*.m",FileNameJoin[{$GraphDataDirectory,"Nodes","WellCovered"}]]

Table[Total[Boole[Equal@@@Transpose[Get[FileNameJoin[{$GraphDataDirectory,"Nodes",#,#<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]]&/@{"MaximalIndependentVertexSetCount","MaximumIndependentVertexSetCount"}]]],{n,10}]//Timing

Image

All

wc=Table[Select[GraphData[n],(WellCoveredQ[GraphData[#]]&)],{n,5}];

GraphicsGrid[Map[Show[GraphData[#,"Image"],PlotLabel->TextCell[Style[GraphData[#,"Name"],Italic],TextAlignment->Center,PageWidth->80]]&,Flatten[Partition[#,6,6,{1,1},{}]&/@wc,1],{2}],ImageSize->500,Dividers->All]

Connected

wc=Table[Select[GraphData["Connected",n],(WellCoveredQ[GraphData[#]]&)],{n,5}];

GraphicsGrid[Map[Show[GraphData[#,"Image"],PlotLabel->TextCell[Style[GraphData[#,"Name"],Italic],TextAlignment->Center,PageWidth->80]]&,Flatten[Partition[#,6,6,{1,1},{}]&/@wc,1],{2}],ImageSize->500,Dividers->All]

Classes

GraphClassesThatAreClass["WellCovered"]

Data

True

l1=SortBy[Select[GraphData["MaximalIndependentVertexSets","Defined"], Equal@@(Length/@GraphData[#,"MaximalIndependentVertexSets"])&],GraphData[#,"V"]&];

l2=SortBy[Select[Intersection@@(GraphData[#,"Defined"]&/@{"MaximumIndependentVertexSets","MaximalIndependentVertexSets"}), GraphData[#,"MaximumIndependentVertexSets"]==GraphData[#,"MaximalIndependentVertexSets"]&],GraphData[#,"V"]&]

Complement[l2,l1]

False

l2=SortBy[Select[Intersection@@(GraphData[#,"Defined"]&/@{"MaximumIndependentVertexSets","MaximalIndependentVertexSets"}), GraphData[#,"MaximumIndependentVertexSets"]=!=GraphData[#,"MaximalIndependentVertexSets"]&],GraphData[#,"V"]&]

GraphData["ThreeP3","MaximumIndependentVertexSets"]

GraphData["ThreeP3","MaximalIndependentVertexSets"]

Algorithms

"AllSets"

DeleteCases[Monitor[{g=#,GraphData[#,"WellCovered"],WellCoveredGraphQ[GraphData[#],Method->"AllSets"]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,GraphData[#,"WellCovered"],WellCoveredGraphQ[GraphData[#],Method->"AllSets"]}&/@GraphData[;;20],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,GraphData[#,"WellCovered"],WellCoveredGraphQ[GraphData[#],Method->"AllSets"]}&/@GraphData[;;50],g],{_,x_,x_}]//Timing

DeleteCases[%[[2]],{_,_,$Failed}]

DeleteCases[Monitor[{g=#,GraphData[#,"WellCovered"],WellCoveredGraphQ[GraphData[#],Method->"AllSets",MaxIterations->10^5]}&/@GraphData[;;50],g],{_,x_,x_}]//Timing

DeleteCases[%[[2]],{_,_,$Failed}]

DeleteCases[Monitor[{g=#,GraphData[#,"WellCovered"],WellCoveredGraphQ[GraphData[#],Method->"AllSets",MaxIterations->10^6]}&/@GraphData[;;50],g],{_,x_,x_}]//Timing

DeleteCases[%[[2]],{_,_,$Failed}]

"EachSize"

DeleteCases[Monitor[{g=#,GraphData[#,"WellCovered"],WellCoveredGraphQ[GraphData[#],Method->"EachSize"]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,GraphData[#,"WellCovered"],WellCoveredGraphQ[GraphData[#],Method->"EachSize"]}&/@GraphData[;;20],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,GraphData[#,"WellCovered"],WellCoveredGraphQ[GraphData[#],Method->"EachSize"]}&/@GraphData[;;50],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,GraphData[#,"WellCovered"],WellCoveredGraphQ[GraphData[#],Method->"EachSize"]}&/@GraphData[;;100],g],{_,x_,x_}]//Timing