Tree Leaf

Author

Eric W. Weisstein
March 10, 2017

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

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

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

Enumeration

Graphs

ShowGraphArray[Map[Highlight[#,Flatten[Position[Degrees[#],1]],HighlightedVertexColors->{Green},HighlightedVertexStyle->Disk[.18]]&,
Graphs/@Range[4],
{2}
],VertexStyle->Disk[.18]]

Plus@@@Map[Leaves,Graphs/@Range[9],{2}]//Timing

A055540

Labeled Graphs

ShowGraphArray[Map[Highlight[#,Flatten[Position[Degrees[#],1]],HighlightedVertexColors->{Green},HighlightedVertexStyle->Disk[.18]]&,
LabeledGraphs/@Range[3],
{2}
],VertexStyle->Disk[.18]]

Plus@@@Map[Leaves,LabeledGraphs/@Range[6],{2}]//Timing

Plus@@@Map[Leaves,LabeledGraphs/@Range[7],{2}]//Timing

A095338

Labeled Trees

ShowGraphArray[Map[Highlight[#,Flatten[Position[Degrees[#],1]],HighlightedVertexColors->{Green},HighlightedVertexStyle->Disk[.18]]&,
LabeledTrees/@Range[3],
{2}
],VertexStyle->Disk[.18]]

Plus@@@Map[Leaves,LabeledTrees/@Range[5],{2}]//Timing

Plus@@@Map[Leaves,LabeledTrees/@Range[6],{2}]//Timing

Plus@@@Map[Leaves,LabeledTrees/@Range[7],{2}]//Timing

A055541

Planted Trees

ShowGraphArray[Map[Highlight[#,Flatten[Position[Degrees[#],1]],HighlightedVertexColors->{Green},HighlightedVertexStyle->Disk[.18]]&,
DeleteCases[PlantedTrees/@Range[6],{}],
{2}
],VertexStyle->Disk[.18]]

Plus@@@Map[Leaves,PlantedTrees/@Range[12],{2}]//Timing

Planted Trees Excluding Root Node

ShowGraphArray[Map[Highlight[#,DeleteCases[Flatten[Position[Degrees[#],1]],1],HighlightedVertexColors->{Green},HighlightedVertexStyle->Disk[.18]]&,
DeleteCases[PlantedTrees/@Range[6],{}],
{2}
],VertexStyle->Disk[.18]]

Plus@@@Map[Leaves,PlantedTrees/@Range[12],{2}]

Plus@@@Map[Leaves,PlantedTrees/@Range[12],{2}]-Length/@PlantedTrees/@Range[12]//Timing

Plus@@@Map[NonRootLeaves,PlantedTrees/@Range[12],{2}]//Timing

A0003227

Rooted Trees including Root Node

ShowGraphArray[Map[Highlight[#,Flatten[Position[Degrees[#],1]],HighlightedVertexColors->{Green},HighlightedVertexStyle->Disk[.18]]&,
RootedTrees/@Range[5],
{2}
],VertexStyle->Disk[.18]]

Plus@@@Map[Leaves,RootedTrees/@Range[12],{2}]//Timing

Rooted Trees excluding Root Node (Same as Planted Trees excluding root node)

ShowGraphArray[Map[Highlight[#,DeleteCases[Flatten[Position[Degrees[#],1]],1],HighlightedVertexColors->{Green},HighlightedVertexStyle->Disk[.18]]&,
RootedTrees/@Range[5],
{2}
],VertexStyle->Disk[.18]]

NonRootLeaves[g_Graph]:=Count[Rest[Degrees[g]],1]

Plus@@@Map[NonRootLeaves,RootedTrees/@Range[12],{2}]//Timing

Trees

ShowGraphArray[Map[Highlight[#,Flatten[Position[Degrees[#],1]],HighlightedVertexColors->{Green},HighlightedVertexStyle->Disk[.18]]&,
Trees/@Range[5],
{2}
],VertexStyle->Disk[.18]]

Plus@@@Map[Leaves,Trees/@Range[14],{2}]//Timing

A003228

Checks

DeleteCases[{GraphData[#,"LeafCount"],Length@Leaves[GraphData[#]]}&/@GraphData[;;10],{x_,x_}]//Timing

DeleteCases[{GraphData[#,"LeafCount"],Length@Leaves[GraphData[#]]}&/@GraphData[;;20],{x_,x_}]//Timing

DeleteCases[{GraphData[#,"LeafCount"],Length@Leaves[GraphData[#]]}&/@GraphData[;;50],{x_,x_}]//Timing

DeleteCases[{GraphData[#,"LeafCount"],Length@Leaves[GraphData[#]]}&/@GraphData[;;100],{x_,x_}]//Timing