Labeled Graph

Author

Eric W. Weisstein
November 9, 2022

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

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

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

Usage

?LabeledGraphs

Counts

https://oeis.org/A001187

Length/@LabeledGraphs/@Range[5]//Timing

Length/@LabeledGraphs/@Range[6]//Timing

Length/@LabeledGraphs/@Range[7]//Timing

Plots

ShowGraphArray[LabeledGraphs[3],VertexColor->Red,VertexStyle->Disk[.2],
PlotRange->All,VertexLabel->Range[3],VertexLabelPosition->{-.1,.3},
GraphicsSpacing->.2,AspectRatio->Automatic]

gr[g_Graph,ps_]:=Module[{v=Vertices[g],i},
Graphics[{PointSize[ps],graphic[g],
Table[Text[i,1.4v[[i]]],{i,Length[v]}]},AspectRatio->Automatic,PlotRange->All]
]

Show[GraphicsArray[{
gr[#,.08]&/@LabeledGraphs[2],
Sequence@@Partition[gr[#,.14]&/@LabeledGraphs[3],4]
}],
GraphicsSpacing->{.3,.3}]

Algorithms

https://mathematica.stackexchange.com/questions/275779/how-to-create-all-possible-graphs-that-connect-all-vertices

Horvat

ConnectedLabeledGraphs[n_Integer?Positive]:=Module[
{
k=Binomial[n,2], (*max number of edges*)
symmetrize=#+Transpose[#]&,
adjmats
},
adjmats=symmetrize@PadRight[TakeList[#,Range[n]-1],{n,n}]&/@IntegerDigits[Range[2^k]-1,2,k];
Select[AdjacencyGraph/@Select[adjmats,Total[#,2]/2>=n-1&],ConnectedGraphQ]
]

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

@user293787

allEdges[n_]:=Flatten[Table[UndirectedEdge[i,j],{i,n},{j,i+1,n}]];
ConnectedLabeledGraphs[n_]:=Select[
Map[Graph[Range[n],#]&,Subsets[allEdges[n]]],
ConnectedGraphQ]

Do[
Print[{n,AllConnectedLabeledGraphs[n]//Length//Timing}],
{n,7}]