Minimum Leaf Number

Author

Eric W. Weisstein
July 17, 2021

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

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

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

Parametrized families

traceable=GraphClassesThatAreClass["Traceable"]

GraphDataCountTable["MinimumLeafNumber",{"Centipede"->254667,Sequence@@Thread[traceable->040000],"Cycle"->007395,"Ladder"->007395,"Pan"->007395,"Path"->040000,"Star"->000027,"Wheel"->007395}]

Andrasfai

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

Antiprism

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

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

Table[HighlightGraph[g=GraphData[{"Antiprism",n},"Graph","Labeled"],EdgeList[SelectFirst[SpanningTrees[g],LeavesCount[#]==2&]],GraphHighlightStyle->"Thick"],{n,3,6}]

Apollonian

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

Barbell

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

Bishop n×n

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

BlackBishop n×n

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

Book

Computed up to n=9; inferred beyond

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

Table[Piecewise[{{2,n==1||n==2}},n-1],{n,20}]

Table[HighlightGraph[g=GraphData[{"Book",n},"Graph","Labeled"],
tree=SelectFirst[SpanningTrees[g],LeavesCount[#]==Piecewise[{{2,n==1||n==2}},n-1]&];
Join[EdgeList[tree],Style[#,Blue]&/@Leaves[tree]],
GraphHighlightStyle->"Thick"],{n,6}]

<<MathWorld`Graphs`

CocktailParty

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

Complete

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

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

<<MathWorld`Graphs`

Table[MinimumLeafNumber[CompleteGraph[n]],{n,5}]

SpanningTrees[CompleteGraph[4,VertexLabels->Automatic]]

CompleteBipartite m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"MinimumLeafNumber"],
Piecewise[{{2,m==n}},Abs[m-n]+1]
},{n,20},{m,n}],1],{_,x_,x_}]

Computed explicitly:

{{{2,10},Missing["NotAvailable"],9},{{3,10},Missing["NotAvailable"],8},{{4,8},Missing["NotAvailable"],5},{{4,9},Missing["NotAvailable"],6},{{4,10},Missing["NotAvailable"],7},{{5,7},Missing["NotAvailable"],3},{{5,8},Missing["NotAvailable"],4},{{5,9},Missing["NotAvailable"],5},{{5,10},Missing["NotAvailable"],6},{{6,8},Missing["NotAvailable"],3},{{6,9},Missing["NotAvailable"],4},{{6,10},Missing["NotAvailable"],5},{{7,9},Missing["NotAvailable"],3},{{7,10},Missing["NotAvailable"],4},{{8,10},Missing["NotAvailable"],3}}

DeleteCases[%,{_,_Missing,_Integer}]

CompleteBipartite n×n

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

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

CompleteKPartite K1,1,1,n

Table[GraphData[{"CompleteKPartite",{1,1,1,n}},"MinimumLeafNumber"],{n,2,10}]

CompleteTripartite k×m×n

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

Untraceable:

GraphData[#,"NotationRules","CompleteTripartite"]&/@(Complement@@GraphData/@{"CompleteTripartite","Traceable"})

Cases[Sort@Flatten[Table[{k,m,n,(k+m+n+1>=2 Max[k,m,n])},{n,10},{m,n},{k,m}],2],{i__,False}:>{i}]

Nonhamiltonian:

Cases[Sort@Flatten[Table[{k,m,n,(k+m+n>=2 Max[k,m,n])},{n,10},{m,n},{k,m}],2],{i__,False}:>{i}]

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"MinimumLeafNumber"],
(*
Piecewise[{{2,(k+m+n+1>=2 Max[k,m,n])}},2Max[k,m,n]-(k+m+n)+1];
*)
Max[2,2Max[k,m,n]-(k+m+n)+1]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

DeleteCases[%102,{_,_Missing,_Integer}]

CompleteTripartite n×n×n

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

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

CrossedPrism

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

Crown

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

FindSequenceFunction[seq,n-2]//Factor

CubeConnectedCycle

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

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

Cycle

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

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

Empty

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

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

FibonacciCube

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

FoldedCube

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

Gear

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

Grid m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"MinimumLeafNumber"]
},{n,10},{m,n}],1],{_,2}]

Grid n×n

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

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

Grid k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{m,n}},"MinimumLeafNumber"]
},{n,10},{m,n},{k,m}],2],{_,2}]

Grid n×n×n

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

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

HalvedCube

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

Hanoi

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

Helm

Computed up to n == 4; inferred beyond

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

Table[HighlightGraph[g=GraphData[{"Helm",n},"Graph","Labeled"],Leaves[SelectFirst[SpanningTrees[g],LeavesCount[#]==n&]]],{n,3,5}]

Table[HighlightGraph[g=GraphData[{"Helm",n},"Graph","Labeled"],
tree=SelectFirst[SpanningTrees[g],LeavesCount[#]==n&];
Join[EdgeList[tree],Style[#,Blue]&/@Leaves[tree]],
GraphHighlightStyle->"Thick"],{n,3,6}]

Hypercube

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

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

Keller

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

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

King n×n

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

Knight m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"MinimumLeafNumber"],
Piecewise[{
{1,m==n==1},
{3,m==n==4||(Min[m,n]==3&&(4<Max[m,n]<7))},
{Missing["NotApplicable"],m==n==3||Min[m,n]<3}
},2]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

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

MinimumLeafNumber[GraphData[{"Knight",{4,4}}],Debug->True]//Timing

Ladder

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

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

LadderRung

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

MengerSponge

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

MoebiusLadder

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

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

Table[HighlightGraph[g=GraphData[{"MoebiusLadder",n},"Graph","Labeled"],EdgeList[SelectFirst[SpanningTrees[g],LeavesCount[#]==2&]],GraphHighlightStyle->"Thick"],{n,3,6}]

Mycielski

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

Table[GraphData[{"Mycielski",n},"MinimumLeafNumber"],{n,10}]

Odd

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

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

Pan

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

Table[HighlightGraph[g=GraphData[{"Pan",n},"Graph","Labeled"],EdgeList[SelectFirst[SpanningTrees[g],LeavesCount[#]==2&]],GraphHighlightStyle->"Thick"],{n,3,8}]

Path

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

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

Prism

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

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

Table[HighlightGraph[g=GraphData[{"Prism",n},"Graph","Labeled"],EdgeList[SelectFirst[SpanningTrees[g],LeavesCount[#]==2&]],GraphHighlightStyle->"Thick"],{n,3,6}]

Queen n×n

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

Rook n×n

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

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

RookComplement n×n

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

SierpinskiCarpet

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

SierpinskiSieve

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

SierpinskiTetrahedron

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

Star

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

Table[GraphData[{"Star",n},"MinimumLeafNumber"],{n,20}]

Sun

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

Sunlet

Computed up to n == 5; inferred beyond

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

Table[HighlightGraph[g=GraphData[{"Sunlet",n},"Graph","Labeled"],Leaves[SelectFirst[SpanningTrees[g],LeavesCount[#]==n&]]],{n,3,5}]

FindSequenceFunction[seq,n-2]//Factor

Tetrahedral

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

TorusGrid n×n

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

Transposition

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

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

Triangular

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

FindSequenceFunction[seq,n-2]//Factor

TriangularGrid

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

Web

Computed up to n = 7; inferred beyond

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

Table[HighlightGraph[g=GraphData[{"Web",n},"Graph","Labeled"],Leaves[SelectFirst[SpanningTrees[g],LeavesCount[#]==n&]]],{n,3,5}]

Table[HighlightGraph[g=GraphData[{"Web",n},"Graph","Labeled"],
tree=SelectFirst[SpanningTrees[g],LeavesCount[#]==n&];
Join[EdgeList[tree],Style[#,Blue]&/@Leaves[tree]],
GraphHighlightStyle->"Thick"],{n,3,5}]

Wheel

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

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

Table[HighlightGraph[g=GraphData[{"Wheel",n},"Graph","Labeled"],EdgeList[SelectFirst[SpanningTrees[g],LeavesCount[#]==2&]],GraphHighlightStyle->"Thick"],{n,4,8}]

WhiteBishop n×n

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

Algorithms

NextSubset

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

DeleteCases[Monitor[{g=#,GraphData[#,"MinimumLeafNumber"],MinimumLeafNumber[GraphData[#],Method ->"NextSubset"]}&/@GraphData["Connected",;;8],g],{_,x_,x_}]//Timing

SpanningTrees

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

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

Subsets

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

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