Chordal Graph

Author

Eric W. Weisstein
May 30, 2017

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

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

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

Counts

Connected

A048192

Table[Total[Boole[ChordalGraphQ/@ConnectedGraphs[n]]],{n,8}]//Timing

Table[Total[Boole[ChordalGraphQ/@ConnectedGraphs[n]]],{n,10}]//Timing

SetDirectory[FileNameJoin[{$GraphDataDirectory,"Nodes","Chordal"}]]

Table[Total[Boole[Get["Chordal_"<>If[n<10,"0",""]<>ToString[n]<>".m"][[ConnectedGraphIndices[n]]]]],{n,10}]

Table[Length@GraphData[{"Chordal","Connected"},n],{n,8}]

Disconnected

A287427

A048193={1,2,4,10,27,94,393,2119,14524,126758,1392387,19109099,326005775,6905776799};

A048192={1,1,2,5,15,58,272,1614,11911,109539,1247691,17566431,305310547,6558690953};

{1,2,4,10,27,94,393,2119}-{1,1,2,5,15,58,272,1614}

A048193-A048192

Table[Total[Boole[Get["Chordal_"<>If[n<10,"0",""]<>ToString[n]<>".m"][[DisconnectedGraphIndices[n]]]]],{n,10}]

Table[Length@GraphData[{"Chordal","Disconnected"},n],{n,8}]

All

A048193

Table[Total[Boole[ChordalGraphQ/@Graphs[n]]],{n,8}]//Timing

Table[Total[Boole[ChordalGraphQ/@Graphs[n]]],{n,10}]//Timing

Table[Total[Boole[Get["Chordal_"<>If[n<10,"0",""]<>ToString[n]<>".m"]]],{n,10}]

Table[Length@GraphData["Chordal",n],{n,8}]

Figure

Table

GraphicsGrid[Map[Show[GraphData[#,"Image"],PlotLabel->TextCell[Style[GraphData[#,"Name"],Italic],TextAlignment->Center]]&,Flatten[Partition[#,5,5,{1,1},{}]&/@Table[GraphData["Chordal",n],{n,4}],1],{2}],Alignment->Top,ImageSize->500,Dividers->All]

GraphicsGrid[Map[Show[GraphData[#,"Image"],PlotLabel->TextCell[Style[GraphData[#,"Name"],Italic],TextAlignment->Center,PageWidth->90]]&,Flatten[Partition[#,5,5,{1,1},{}]&/@Table[GraphData[{"Chordal","Connected"},n],{n,5}],1],{2}],Alignment->Top,ImageSize->500,Dividers->All]

GraphicsGrid[Map[Show[GraphData[#,"Image"],PlotLabel->TextCell[Style[GraphData[#,"Name"],Italic],TextAlignment->Center,PageWidth->90]]&,Flatten[Partition[#,5,5,{1,1},{}]&/@Table[GraphData[{"Chordal","Connected"},n],{n,4}],1],{2}],Alignment->Top,Dividers->All]

Chords

ChordalQ[Cycle[4]]

GraphCycles[CompleteGraph[4]]

Off[Graphics::"gprim"]

g=CompleteGraph[4];
ShowGraphArray[Partition[
Highlight[Highlight[g,{Partition[#,2,1]},HighlightedEdgeColors->{Red},
HighlightedEdgeStyle->Thickness[.05]],
{Chords[g,#]},
HighlightedEdgeStyle->Thickness[.04],
HighlightedEdgeColors->{Blue}]&/@Sort[GraphCycles[g]],
10,10,{1,1},{}],
VertexStyle->Disk[.1],PlotRange->All]

Chords[CompleteGraph[4],#]&/@GraphCycles[CompleteGraph[4]]

Counts

Chordal

A048193

1, 2, 4, 10, 27, 94, 393, 2119, 14524, 126758, 1392387

Timing[Length/@(chordal=Table[Position[Graphs[n,"Format"->"V7"],_?(ChordalQ[#,Method->"ChordlessCycles"]&),1]//Flatten,{n,6}])]

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

Timing[Length/@(chordal=Table[Position[Graphs[n,"Format"->"V7"],_?(ChordalQ[#,Method->"ChordlessCycles"]&),1]//Flatten,{n,7}])]

Timing[Length/@(chordal=Table[Position[Graphs[n,"Format"->"V7"],_?(ChordalQ[#,Method->"TreeDecomposition"]&),1]//Flatten,{n,6}])]

Timing[Length/@(chordal=Table[Position[Graphs[n,"Format"->"V7"],_?(ChordalQ[#,Method->"TreeDecomposition"]&),1]//Flatten,{n,7}])]

Chordal Connected

A048192

1, 1, 2, 5, 15, 58, 272, 1614, 11911, 109539, 1247691, 17566431

Timing[Length/@(cchordal=Table[Select[Graphs[n,"Format"->"V7"][[chordal[[n]]]],ConnectedQ],{n,Length[chordal]}])]

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

Nonchordal

Length/@(nonchordal=Table[Complement[Range[Length[Graphs[n]]],chordal[[n]]],{n,Length[chordal]}])

Timing[Length/@(cnonchordal=Table[Select[Graphs[n][[nonchordal[[n]]]],ConnectedQ],{n,Length[chordal]}])]

Missing

SortBy[GraphData["Chordal","Missing"],GraphData[#,"V"]&]

SortBy[Select[GraphData[All],GraphData[#,"ChordlessCycles"]===Missing["NotAvailable"]&],GraphData[#,"V"]&]

Compute

GraphData[gn={"CocktailParty",6},"Chordal"]

alpha=GraphData[gn,"IndependenceNumber"]

FindChordlessCycle[GraphData[{"CocktailParty",6}],Debug->True]

{“Johnson”,{10,5}}

{gn={"Johnson",{10,5}},FindChordlessCycle[GraphData[gn],Method->"Paths","InitialVertices"->If[GraphData[gn,"Symmetric"],GraphData[gn,"EdgeIndices"][[1]],{}],"IndependenceNumber"->GraphData[gn,"IndependenceNumber"],Debug->True]//Timing}

{“Cage”,{8,8}}

GraphData[gn={"Cage",{8,8}},{"Symmetric","VertexTransitive"}]

{gn={"Cage",{8,8}},MemoryConstrained[FindChordlessCycle[GraphData[gn],Method->"Paths","InitialVertices"->If[GraphData[gn,"Symmetric"],GraphData[gn,"EdgeIndices"][[1]],{}],"IndependenceNumber"->GraphData[gn,"IndependenceNumber"],Debug->True],80*^9]//Timing}

{gn={"Cage",{8,8}},MemoryConstrained[FindChordlessCycle[GraphData[gn],Method->"Paths","InitialVertices"->GraphData[gn,"EdgeIndices"][[1]],"IndependenceNumber"->GraphData[gn,"IndependenceNumber"],Debug->True],80*^9]//Timing}

{“Keller”,5}

edge=(edges=GraphData[gn,"EdgeIndices"])[[1]]

Take[Complement[Union[Flatten[Select[edges,!FreeQ[#,7]&]]],{1,7}],10]

{gn={"Keller",5},MemoryConstrained[FindChordlessCycle[GraphData[gn],Method->"Paths","InitialVertices"->{1,7,9},"IndependenceNumber"->GraphData[gn,"IndependenceNumber"],Debug->True],80*^9]//Timing}

{“Mycielski”,11}

edge=(edges=GraphData[gn={"Mycielski",11},"EdgeIndices"])[[1]]

Take[Complement[Union[Flatten[Select[edges,!FreeQ[#,2]&]]],{1,2}],10]

{gn,MemoryConstrained[FindChordlessCycle[GraphData[gn],Method->"Paths","InitialVertices"->{1,2,4},"IndependenceNumber"->GraphData[gn,"IndependenceNumber"],Debug->True],80*^9]//Timing}

{“Cage”,{10,8}}

edge=(edges=GraphData[gn={"Cage",{10,8}},"EdgeIndices"])[[1]]

Take[Complement[Union[Flatten[Select[edges,!FreeQ[#,821]&]]],{1,821}],All]

{gn={"Cage",{10,8}},MemoryConstrained[FindChordlessCycle[GraphData[gn],Method->"Paths","InitialVertices"->{1,821,11},"IndependenceNumber"->GraphData[gn,"IndependenceNumber"],Debug->True],80*^9]//Timing}

{“Cage”,{10,8}}

edge=(edges=GraphData[gn={"Cage",{12,8}},"EdgeIndices"])[[1]]

Take[Complement[Union[Flatten[Select[edges,!FreeQ[#,1465]&]]],{1,1465}],All]

{gn={"Cage",{12,8}},MemoryConstrained[FindChordlessCycle[GraphData[gn],Method->"Paths","InitialVertices"->{1,1465,13},"IndependenceNumber"->GraphData[gn,"IndependenceNumber"],Debug->True],80*^9]//Timing}

{“Kneser”,{14,6}

{gn={"Kneser",{14,6}},MemoryConstrained[FindChordlessCycle[GraphData[gn],Method->"Paths",If[GraphData[gn,"Symmetric"]===True,"InitialVertices"->GraphData[gn,"EdgeIndices"][[1]],Sequence@@{}],"IndependenceNumber"->GraphData[gn,"IndependenceNumber"],Debug->True],80*^9]//Timing}

{“Cage”,{14,8}}

edge=(edges=GraphData[gn={"Cage",{14,8}},"EdgeIndices"])[[1]]

Take[Complement[Union[Flatten[Select[edges,!FreeQ[#,2381]&]]],{1,2381}],All]

{gn={"Cage",{14,8}},MemoryConstrained[FindChordlessCycle[GraphData[gn],Method->"Paths","InitialVertices"->{1,2381,15},"IndependenceNumber"->GraphData[gn,"IndependenceNumber"],Debug->True],80*^9]//Timing}