Claw-Free Graph

Author

Eric W. Weisstein
April 26, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Claw-FreeGraph.nb.

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

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

The Claw

Show[GraphData["ClawGraph"]//StyleGraphs,ImageSize->Small]

Claw is a subgraph but not an induced subgraph

bug(419268): Subgraph and FindIsomorphicSubgraph are inconsistent (the first gives a vertex-induced subgraph; the latter a normal subgraph) [declared AsDesigned]

bug(414735): Implement FindInducedSubgraphIsomorphism etc. (in addition to FindSubgraphIsomorphism)

{g=GraphData[{5,31},"Graph","Labeled"],
claw=CompleteGraph[{3,1},VertexLabels->Automatic]}

LAD

g is a subgraph of the claw:

IGraphM`IGLADSubisomorphicQ[claw,g]

but not an *induced* subgraph:

IGraphM`IGLADSubisomorphicQ[claw,g,"Induced"->True]

Built-in

IsomorphicSubgraphQ[claw,g]

InducedSubgraphQ[g,claw]

Induced subgraph (Graphs.m)

EdgeInducedSubgraphFreeQ

Subgraph

FindIsomorphicSubgraph finds (normal, not induced) subgraphs:

FindIsomorphicSubgraph[g,claw]

isorules=FindSubgraphIsomorphism[claw,g]

iso=Normal[isorules][[1,All,-1]]

But Subgraph gives the vertex-induced subgraph:

Subgraph[g,iso]

EdgeList[g]

edges=Select[EdgeList[g],MatchQ[#,UndirectedEdge[Alternatives@@iso,Alternatives@@iso]]&]

HighlightGraph[g,Join[iso,edges]]

Counts

All

A086991

1, 2, 4, 10, 26, 85, 302, 1285, 6170, 34294, 227417, 2001617, 26098641, 520051389, 15041205304

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

$Version

DateString[]

Count[#,_?ClawFreeGraphQ]&/@Graphs/@Range[8]//Timing

Connected

A022562

1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, 1728404, 23805256, 491544474, 14491876320

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

Do[Print[{n,Length[ConnectedGraphs[n]]//Timing}],{n,8}];

$Version

DateString[]

Count[#,_?ClawFreeGraphQ]&/@ConnectedGraphs/@Range[8]//Timing

Count[#,_?ClawFreeGraphQ]&/@ConnectedGraphs/@Range[9]//Timing

Disconnected

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

Enumeration

Connected

clawfree=Table[SortBy[GraphData[{"Connected","ClawFree"},n],GraphData[#,"M"]&],{n,5}]

GraphicsGrid[Flatten[Partition[#,UpTo[7]]&/@
Map[
Show[
StyleGraphs[GraphData[#],VertexSize->If[#==="SingletonGraph",.015,{"Scaled",.05}]],PlotLabel->Style[GraphData[#,"Name"],Directive[Black,Italic,FontFamily->"Times"]]
]&,
clawfree,
{2}
],1],Alignment->Top,ImageSize->800,Dividers->All]

All

clawfree=Table[SortBy[GraphData["ClawFree",n],GraphData[#,"M"]&],{n,5}]

GraphicsGrid[Flatten[Partition[#,UpTo[7]]&/@
Map[
Show[
StyleGraphs[GraphData[#],VertexSize->If[#==="SingletonGraph",.015,{"Scaled",.05}]],PlotLabel->Style[GraphData[#,"Name"],Directive[Black,Italic,FontFamily->"Times"]]
]&,
clawfree,
{2}
],1],Alignment->Top,ImageSize->800,Dividers->All]

Classes

GraphClassesThatAreClass["ClawFree"]

Table

Grid[SortBy[GraphData[#,{"Name","V"}]&/@Cases[GraphData["ClawFree",;;20],_String],Last],Alignment->{{Left,Right},Automatic},Dividers->All]

Algorithms

<<MathWorld`Graphs`

"InducedSubgraph"

(bad=DeleteCases[Monitor[{
gn=#,
GraphData[#,"ClawFree"],
ClawFreeGraphQ[GraphData[#],Method->"InducedSubgraph"]
}&/@GraphData[;;10],gn],
{_,x_,x_}
])//Timing

(bad=DeleteCases[Monitor[{
gn=#,
GraphData[#,"ClawFree"],
ClawFreeGraphQ[GraphData[#],Method->"InducedSubgraph"]
}&/@GraphData[All],gn],
{_,x_,x_}
])//Timing

l={#,{0,#3}}&@@@bad

MissingFillin[l,"ClawFree"]

RenameGraphFiles[]

"SubgraphIsomorphism"

DeleteCases[
Monitor[{gn=#,GraphData[#,"ClawFree"],ClawFreeGraphQ[GraphData[#],Method->"InducedSubgraph"]}&/@GraphData["Connected",;;10],gn],
{_,x_,x_}]//Timing

DeleteCases[
Monitor[{gn=#,GraphData[#,"ClawFree"],ClawFreeGraphQ[GraphData[#],Method->"InducedSubgraph"]}&/@GraphData[All],gn],
{_,x_,x_}]//Timing

"TriangleFreeComplementSubgraphs"

DeleteCases[Monitor[{
gn=#,
GraphData[#,"ClawFree"],
ClawFreeGraphQ[GraphData[#],Method->"TriangleFreeComplementSubgraphs"]
}&/@GraphData[;;10],gn],
{_,x_,x_}
]//Timing