Maximum Leaf Number

Author

Eric W. Weisstein
July 12, 2021

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

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

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

Parametrized families

Remember to update ConnectedDominationNumber as well

GraphDataCountTable["MaximumLeafNumber",{"Antiprism"->000027,"Cycle"->007395,"Gear"->032766,"Keller"->058896,"MoebiusLadder"->000027,"Path"->040000}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"MaximumLeafNumber"],{n,10}]

FindSequenceFunction[Rest@seq,n-1]//Factor

Antiprism

A000027

Entity["Graph",{"Antiprism",n}]["MaximumLeafNumber"]

Table[GraphData[{"Antiprism",n},"MaximumLeafNumber"],{n,3,25}]

Apollonian

A258597

seq=Table[GraphData[{"Apollonian",n},"MaximumLeafNumber"],{n,6}]

Table[GraphData[{"Apollonian",n},"V"],{n,6}]

FindSequenceFunction[%,n]

FullSimplify[(1/2) (5+(3^n))-(3^(n-3)+5)/2]

seq=Table[Piecewise[{{3,n==1},{6,n==2}},13 (3^(-3+n))],{n,20}]

seq=13 3^Range[0,20]

FindLinearRecurrence[seq]

LinearRecurrence[{3},{13},20]

gf=FindGeneratingFunction[seq,x]

CoefficientList[Series[-(13/(-1+3 x)),{x,0,20}],x]

CoefficientList[Series[13/(1-3 x),{x,0,20}],x]

Barbell

seq=Table[GraphData[{"Barbell",n},"MaximumLeafNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Factor

Bishop n×n

Table[GraphData[{"Bishop",{n,n}},"MaximumLeafNumber"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"MaximumLeafNumber"],{n,10}]

Table[VertexCount[BlackBishopGraph[n,n]],{n,10}]

FullSimplify[FindSequenceFunction[%,n],n∈Integers]

FindSequenceFunction[DeleteMissing@Drop[seq,2],n]

FullSimplify[(1/4) (1+(((-1))^(1+n))+2 (n^2))-(n-2)]

Table[Piecewise[{{1,n==1}},(1/4) (9+(((-1))^(1+n))+2 (-2+n) n)],{n,10}]

Book

seq=Table[GraphData[{"Book",n},"MaximumLeafNumber"],{n,20}]

FindSequenceFunction[seq,n]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"MaximumLeafNumber"],{n,20}]

FindSequenceFunction[Rest@seq,n-1]//Factor

Complete

Entity["Graph",{"Complete",n}]["MaximumLeafNumber"]

Table[GraphData[{"Complete",n},"MaximumLeafNumber"],{n,10}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["MaximumLeafNumber"]

DeleteCases[Block[{m,n},{#,GraphData[#,"MaximumLeafNumber"],{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"];Piecewise[{{2, m == n == 1}, {-1 + m + n, Min[m, n] == 1}}, -2 + m + n]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["MaximumLeafNumber"]

Table[GraphData[{"CompleteBipartite",{n,n}},"MaximumLeafNumber"],{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["MaximumLeafNumber"]

DeleteCases[Block[{k,m,n},{#,GraphData[#,"MaximumLeafNumber"],{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"];Piecewise[{{-1 + k + m + n, Min[k, m, n] == 1}}, -2 + k + m + n]}]&/@GraphData["CompleteTripartite"],{_,x_,x_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["MaximumLeafNumber"]

Table[GraphData[{"CompleteTripartite",{n,n,n}},"MaximumLeafNumber"],{n,10}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"MaximumLeafNumber"],{n,2,10}]

Crown

seq=Table[GraphData[{"Crown",n},"MaximumLeafNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Factor

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["MaximumLeafNumber"]

Table[GraphData[{"CubeConnectedCycle",n},"MaximumLeafNumber"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["MaximumLeafNumber"]

Table[GraphData[{"Cycle",n},"MaximumLeafNumber"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["MaximumLeafNumber"]

Table[GraphData[{"Empty",n},"MaximumLeafNumber"],{n,30}]

FibonacciCube

Table[GraphData[{"FibonacciCube",n},"MaximumLeafNumber"],{n,15}]

FoldedCube

Table[GraphData[{"FoldedCube",n},"MaximumLeafNumber"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"MaximumLeafNumber"],{n,3,20}]

Table[If[Mod[n,2]==1,(3n-1)/2,3n/2],{n,3,20}]

Table[Floor[3n/2],{n,3,20}]

%==seq

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["MaximumLeafNumber"]

DeleteCases[Block[{m,n},{#,GraphData[#,"MaximumLeafNumber"],{m,n}="Grid"/.GraphData[#,"NotationRules"];XXX}]&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==2&],{_,x_,x_}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["MaximumLeafNumber"]

Table[GraphData[{"Grid",{n,n}},"MaximumLeafNumber"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["MaximumLeafNumber"]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["MaximumLeafNumber"]

Table[GraphData[{"Grid",{n,n,n}},"MaximumLeafNumber"],{n,10}]

HalvedCube

Table[GraphData[{"HalvedCube",n},"MaximumLeafNumber"],{n,2,10}]

Hanoi

Table[GraphData[{"Hanoi",n},"MaximumLeafNumber"],{n,5}]

Helm

Table[GraphData[{"Helm",n},"MaximumLeafNumber"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["MaximumLeafNumber"]

Table[GraphData[{"Hypercube",n},"MaximumLeafNumber"],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["MaximumLeafNumber"]

Table[(4^n)-4,{n,5}]

FullSimplify[(4^n)-4]

Table[GraphData[{"Keller",n},"MaximumLeafNumber"],{n,5}]

King n×n

Table[GraphData[{"King",{n,n}},"MaximumLeafNumber"],{n,10}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["MaximumLeafNumber"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["MaximumLeafNumber"]

Table[GraphData[{"Knight",{n,n}},"MaximumLeafNumber"],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["MaximumLeafNumber"]

Table[GraphData[{"Ladder",n},"MaximumLeafNumber"],{n,20}]

LadderRung

Table[GraphData[{"LadderRung",n},"MaximumLeafNumber"],{n,5}]

MengerSponge

Table[GraphData[{"MengerSponge",n},"MaximumLeafNumber"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["MaximumLeafNumber"]

Table[GraphData[{"MoebiusLadder",n},"MaximumLeafNumber"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["MaximumLeafNumber"]

Table[GraphData[{"Mycielski",n},"MaximumLeafNumber"],{n,2,10}]

Odd

Entity["Graph",{"Odd",n}]["MaximumLeafNumber"]

Table[GraphData[{"Odd",n},"MaximumLeafNumber"],{n,7}]

Pan

Table[GraphData[{"Pan",n},"MaximumLeafNumber"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["MaximumLeafNumber"]

Table[GraphData[{"Path",n},"MaximumLeafNumber"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["MaximumLeafNumber"]

Table[GraphData[{"Prism",n},"MaximumLeafNumber"],{n,3,25}]

Queen n×n

Table[GraphData[{"Queen",{n,n}},"MaximumLeafNumber"],{n,10}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"MaximumLeafNumber"],{n,10}]

FindSequenceFunction[Rest@seq,n-1]//Factor

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"MaximumLeafNumber"],{n,10}]

Table[GraphData[{"RookComplement",{n,n}},"V"],{n,10}]

Table[Piecewise[{{1,n==1},{Missing["NotApplicable"],n==2}},n^2-3],{n,10}]

SierpinskiCarpet

Table[GraphData[{"SierpinskiCarpet",n},"MaximumLeafNumber"],{n,4}]

SierpinskiSieve

Table[GraphData[{"SierpinskiSieve",n},"MaximumLeafNumber"],{n,5}]

SierpinskiTetrahedron

Table[GraphData[{"SierpinskiTetrahedron",n},"MaximumLeafNumber"],{n,6}]

Star

Entity["Graph",{"Star",n}]["MaximumLeafNumber"]

Table[GraphData[{"Star",n},"MaximumLeafNumber"],{n,3,20}]

Sun

seq=Table[GraphData[{"Sun",n},"MaximumLeafNumber"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"MaximumLeafNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Factor

Tetrahedral

Probably Binomial[n, 3] - 2 (n - 4)

Table[GraphData[{"Tetrahedral",n},"MaximumLeafNumber"],{n,6,10}]

Binomial[n,3]-2(n-4)//Factor

Table[Binomial[n,3]-2(n-4),{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"MaximumLeafNumber"],{n,3,10}]

Transposition

Entity["Graph",{"Transposition",n}]["MaximumLeafNumber"]

Table[GraphData[{"Transposition",n},"MaximumLeafNumber"],{n,6}]

Triangular

seq=Table[GraphData[{"Triangular",n},"MaximumLeafNumber"],{n,3,10}]

FindSequenceFunction[seq,n-2]//Factor

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"MaximumLeafNumber"],{n,10}]

Table[GraphData[{"TriangularGrid",n},"V"],{n,10}]

FindSequenceFunction[%,n]//Factor

FullSimplify[Binomial[n+2,2]-2(n-1)]

Binomial[n,2]+3

Table[Piecewise[{{2,n==1}},Binomial[n,2]+3],{n,10}]

Web

seq=Table[GraphData[{"Web",n},"MaximumLeafNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Factor

Wheel

Entity["Graph",{"Wheel",n}]["MaximumLeafNumber"]

Table[GraphData[{"Wheel",n},"MaximumLeafNumber"],{n,4,20}]

WhiteBishop n×n

Table[GraphData[{"WhiteBishop",{n,n}},"MaximumLeafNumber"],{n,2,10}]

Table[GraphData[{"WhiteBishop",{n,n}},"V"],{n,2,10}]

FindSequenceFunction[%,n-1]//Factor

FullSimplify[(1/4) (-2+(((-1))^n)+(((-1))^(2 n))+2 (n^2))-(n-2),n∈Integers]

Table[Piecewise[{{2,n==2||n==3}},(1/4) (7+(((-1))^n)+2 (-2+n) n)],{n,2,10}]

Algorithms

<<MathWorld`Graphs`

Examples

{5,31}

g=GraphData[{5,31},"Graph","Labeled"]

trees=SpanningTrees[g]

Leaves/@trees

Max[LeavesCount/@trees]

GraphData[{5,31},"MaximumLeafNumber"]

"BannerGraph"

g=GraphData[gn="BannerGraph","Graph","Labeled"]

trees=SpanningTrees[g]

Leaves/@trees

Max[LeavesCount/@trees]

GraphData[gn,"MaximumLeafNumber"]

ConnectedDominatingSet

DeleteCases[Monitor[{g=#,GraphData[#,"MaximumLeafNumber"],MaximumLeafNumber[GraphData[#],Method->"ConnectedDominatingSet"]}&/@GraphData["Connected",;;7],g],{_,x_,x_}]//Timing

SpanningTrees

DeleteCases[Monitor[{g=#,GraphData[#,"MaximumLeafNumber"],MaximumLeafNumber[GraphData[#],Method->"SpanningTrees"]}&/@GraphData["Connected",;;7],g],{_,x_,x_}]//Timing

Subsets

DeleteCases[Monitor[{g=#,GraphData[#,"MaximumLeafNumber"],MaximumLeafNumber[GraphData[#],Method->"Subsets"]}&/@GraphData["Connected",;;7],g],{_,x_,x_}]//Timing

Algorithms [old]

Combinatorica`Graph

System`Graph Mapped+Selected

SpanningTrees[g_System`Graph]:=Module[{n=VertexCount[g],e,s,edges=List@@@EdgeList[g]},s=Developer`ToPackedArray[Subsets[edges,{n-1}]]//Quiet;
If[Head[s]===Subsets,Return[$Failed]];
Select[System`Graph[UndirectedEdge@@@#]&/@s,TreeGraphQ]]

{MaximumLeafNumber[GraphData[{"CubicPolyhedral",52}]]//Timing,MaxMemoryUsed[]/10^9.GB}

System`Graph Selected

SpanningTrees2[g_System`Graph]:=Module[{n=VertexCount[g],e,s,edges=List@@@EdgeList[g]},s=Developer`ToPackedArray[Subsets[edges,{n-1}]]//Quiet;
If[Head[s]===Subsets,Return[$Failed]];
System`Graph[UndirectedEdge@@@#]&/@
Select[s,TreeGraphQ[System`Graph[UndirectedEdge@@@#]]&]
]
MaximumLeafNumber2[g:(_Combinatorica`Graph|_System`Graph)]:=Module[{trees=SpanningTrees2[g]},If[trees==={},{},Max[LeavesCount/@trees]]]

{MaximumLeafNumber2[GraphData[{"CubicPolyhedral",52}]]//Timing,MaxMemoryUsed[]/10^9.GB}

System`Graph Selected and LeafCount applied directly

LeavesCount[g_System`Graph]:=Count[VertexDegree[g],1]

MaximumLeafNumber4[g_System`Graph]:=Module[{n=VertexCount[g],e,s,edges=List@@@EdgeList[g]},s=Developer`ToPackedArray[Subsets[edges,{n-1}]]//Quiet;
If[Head[s]===Subsets,Return[$Failed]];
Max[Count[VertexDegree[System`Graph[UndirectedEdge@@@#]],1]&/@
Select[s,TreeGraphQ[System`Graph[UndirectedEdge@@@#]]&]]
]

{MaximumLeafNumber4[GraphData[{"CubicPolyhedral",52}]]//Timing,MaxMemoryUsed[]/10^9.GB}

System`Graph Picked

SpanningTrees3[g_System`Graph]:=Module[{n=VertexCount[g],e,s,edges=List@@@EdgeList[g],tf},s=Developer`ToPackedArray[Subsets[edges,{n-1}]]//Quiet;
If[Head[s]===Subsets,Return[$Failed]];
tf=TreeGraphQ[System`Graph[UndirectedEdge@@@#]]&/@s;
System`Graph[UndirectedEdge@@@#]&/@Pick[s,tf,True]
]
MaximumLeafNumber3[g:(_Combinatorica`Graph|_System`Graph)]:=Module[{trees=SpanningTrees3[g]},If[trees==={},{},Max[LeavesCount/@trees]]]

{MaximumLeafNumber3[GraphData[{"CubicPolyhedral",52}]]//Timing,MaxMemoryUsed[]/10^9.GB}