Rooted Graph

Author

Eric W. Weisstein
July 16, 2003

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

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

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

Construction

IsomorphicQ Can't Distinguish Weights

r=Flatten[Outer[SetVertexWeights[#1,#2]&,ListGraphs[3],Permutations[{1,0,0}],1],1]

GetVertexWeights/@r

IsomorphicQ[r[[1]],r[[2]]]

Counts

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

Graphs

ShowGraphArray[
Flatten[
Map[Partition[#,7,7,{1,1},{}]&,
RootedGraphs/@Range[4],
{1}],1]
]

Enumeration

Table[CycleIndex[PairGroup[Append[#,n]&/@SymmetricGroup[n-1]],x],
{n,6}]/.x[n_]:>Subscript[x,n]//ColumnForm//TraditionalForm

(t=Expand[Table[CycleIndex[PairGroup[Append[#,n]&/@SymmetricGroup[n-1]],x],
{n,6}]/.x[n_]:>1+x^n])//ColumnForm

CoefficientList[#,x]&/@t