Graphical Partition

Author

Eric W. Weisstein
May 31, 2004

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

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

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

Enumeration

Graphs on n Nodes with No Isolated Points

?GraphicalPartitionQ

Any graph with no isolated points is a graphical partition

Count[#,_?GraphicalPartitionQ]&/@Graphs/@Range[9]//Timing

Length/@(gp=Select[#,GraphicalPartitionQ]&/@Graphs/@Range[9])//Timing

Count[#,_?(Min[Degrees[#]]>0&)]&/@Graphs/@Range[9]//Timing

This is all of them, and includes those with the same degree sequences

Length/@Union/@Map[DegreeSequence,gp,{2}]

Numbers of distinct graphical partitions corresponding to a graph on n nodes

Graphical Partitions on n Edges

?GraphicalPartitions

Length/@Table[GraphicalPartitions[n],{n,2,7,2}]

This is all with distinct degree sequences, which should be the same as the following

Length/@Table[Union[DegreeSequence/@GraphicalPartitions[n]],{n,2,7,2}]

Count graphs having the same degree sequences only once

Table[Count[RealizeDegreeSequence/@Partitions[n],_Graph],{n,2,20,2}]

gp=Flatten[Table[Select[RealizeDegreeSequence/@Partitions[n],#[[0]]==Graph&],{n,2,20,2}]];

Table[Count[gp,_?(V[#]==n&)],{n,10}]

gr[g_]:=Graphics[{PointSize[.16],graphic[g],
Text[DegreeSequence[g],{0,-1.7}]},AspectRatio->Automatic]

Show[GraphicsArray[{
gr/@GraphicalPartitions[2],
gr/@GraphicalPartitions[4],
gr/@GraphicalPartitions[6]
}],PlotRange->All,GraphicsSpacing->{.8,.3}]

Two topologically distinct graphs can have the same degree sequence

gr[g_]:=Graphics[{PointSize[.08],graphic[g],
Text[DegreeSequence[g],{0,-1.7}]},AspectRatio->Automatic]

DegreeSequence/@GraphicalPartitions[8]

Show[GraphicsArray[{
gr/@GraphicalPartitions[8][[{5,6}]]
}]]