Chordless Graph

Author

Eric W. Weisstein
May 31, 2017

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

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

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

Counts

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

Connected

A287693

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

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

GraphicsGrid[Table[GraphData/@GraphData[{"Chordless","Connected"},n]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.02,{"Scaled",.06}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,4}],Dividers->All]

ChordlessGraphQ[System`Graph[{1,2},{}]]

ChordlessGraphQ[System`Graph[{1,2},{1\[UndirectedEdge]2}]]

Table[ToEntity/@Select[ConnectedGraphs[n],ChordlessGraphQ],{n,5}]//Column

GraphicsGrid[Partition[Select[ConnectedGraphs[4],ChordlessGraphQ],UpTo[4]],Dividers->All]

Graphs can be chordless but not chordal:

data=Table[{#,ChordlessGraphQ[#],ChordalGraphQ[#]}&/@Graphs[n],{n,4}];

Cases[#,{_,True,False}][[All,1]]&/@data

Map[ToEntity,%,{2}]

Graphs can be chordal but not chordless:

Cases[#,{_,False,True}][[All,1]]&/@data

Map[ToEntity,%,{2}]

Graphs can be chordless and chordal:

GraphicsGrid[Cases[#,{_,True,True}][[All,1]]&/@data,Dividers->All]

GraphicsGrid[Partition[Select[ConnectedGraphs[4],ChordalGraphQ],UpTo[4]],Dividers->All]

GraphData["DiamondGraph","ChordlessCycles"]

Table[Length@GraphData[{"Chordless","Connected"},n],{n,12}]

Disconnected

Table[Length@GraphData[{"Chordless","Disconnected"},n],{n,12}]

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

All

A287694

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

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

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

Table[ToEntity/@Select[Graphs[n],ChordlessGraphQ],{n,4}]//Column

GraphicsGrid[Table[GraphData/@GraphData[{"Chordless"},n]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.017,{"Scaled",.08}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,4}],Dividers->All,ImageSize->500]