Arboricity

Author

Eric W. Weisstein
December 17, 2021

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

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

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

Counts

Tally[Sort[#]]&/@(values=Table[Arboricity/@Graphs[n],{n,7}])//Column

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Get/@FileNames["*.m",FileNameJoin[{$GraphDataDirectory,"Nodes","Arboricity"}]]))//Column

Tally[Sort[#]]&/@values//Column

A294218

Flatten[tallies]

A000088

Total/@tallies

A005195

tallies[[All,1]]

Not in OEIS:

tallies[[All,-1]]

Not in OEIS:

Drop[tallies,2][[All,2]]

Not in OEIS:

Drop[tallies,2][[All,-2]]

Length/@tallies

Not in OEIS:

Total/@values

Regular

Table[Floor[n/2]+1,{n,3,8}]

Cubic

Tally[GraphData[#,"Arboricity"]&/@GraphData["Cubic"]]

Quartic

Tally[GraphData[#,"Arboricity"]&/@GraphData["Quartic"]]

Quintic

Tally[GraphData[#,"Arboricity"]&/@GraphData["Quintic"]]

Sextic

Tally[GraphData[#,"Arboricity"]&/@GraphData["Sextic"]]

Septic

Tally[GraphData[#,"Arboricity"]&/@GraphData["Septic"]]

Octic

Tally[GraphData[#,"Arboricity"]&/@GraphData["Octic"]]

Disconnected

GraphData["Disconnected",;;7]

"P2+2K1"

GraphData["P2+2K1"]

Arboricity[GraphData["P2+2K1"]]

2P2+K1

GraphData["2P2+K1"]

Arboricity[GraphData["2P2+K1"]]

C3+2K1

GraphData["C3+2K1"]

Arboricity[GraphData["C3+2K1"]]

2C3

GraphData["2C3"]

Arboricity[GraphData["2C3"]]

Parametrized family table

GraphDataCountTable["Arboricity",{"Alkane"->000012,"Andrasfai"->004526,"Antiprism"->010701,"Barbell"->004526,"Book"->007395,"Centipede"->000012,"CocktailParty"->000027,"Complete"->004526,"CompleteBipartite"->004526,"CompleteTripartite"->000027,"CrossedPrism"->007395,"Crown"->004526,,"Cycle"->007395,"CycleComplement"->004526,"Dipyramid"->010701,"Empty"->000012,"Gear"->007395,{"Grid",2}->040000,"Helm"->007395,"Hypercube"->004526,"Ladder"->040000,"LadderRung"->000012,"MoebiusLadder"->007395,"Pan"->007395,"Path"->000012,"Prism"->007395,"Star"->000012,"Sun"->004526,"Sunlet"->007395,"Triangular"->000027,"TriangularHoneycombQueen"->000027,"TriangularHoneycombRook"->004526,"TriangularSnake"->040000,"Web"->007395,"Wheel"->007395}]

Parametrized families

Andrasfai

Table[GraphData[{"Andrasfai",n},"Arboricity"],{n,10}]

Table[Ceiling[(n+1)/2],{n,10}]

Table[Floor[n/2]+1,{n,10}]

Antiprism

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

seq=Table[GraphData[{"Antiprism",n},"Arboricity"],{n,3,25}]

Monitor[Table[Arboricity[AntiprismGraph[n]],{n,3,7}],n]//Timing

Barbell

Table[GraphData[{"Barbell",n},"Arboricity"],{n,3,20}]

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

Bishop n×n

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

BlackBishop n×n

Table[GraphData[{"BlackBishop",{n,n}},"Arboricity"],{n,2,10}]

Book

Table[GraphData[{"Book",n},"Arboricity"],{n,20}]

Circulant

{#,Arboricity[GraphData[#]]}&/@GraphData["Circulant",;;8]//Column

CocktailParty

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

Complete

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

seq=Table[GraphData[{"Complete",n},"Arboricity"],{n,20}]

Table[Arboricity[System`CompleteGraph[n]],{n,10}]//Timing

Table[Ceiling[n/2],{n,10}]

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{{m,n},GraphData[{"CompleteBipartite",{m,n}},"Arboricity"],Ceiling[((m n)/(m+n-1))]},{n,20},{m,n}],1]m,{_,x_,x_}]

Flatten[Table[Ceiling[((m n)/(m+n-1))]-Arboricity[System`CompleteGraph[{m,n}]],{n,8},{m,n}]]//Union//Timing

CompleteBipartite n×n

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

FullSimplify[Ceiling[((m n)/(m+n-1))]/.m->n]

Table[Arboricity[System`CompleteGraph[{n,n}]],{n,8}]//Timing

Table[Ceiling[((n^2)/(2n-1))],{n,20}]

Table[1+Floor[n/2],{n,20}]

Table[Ceiling[(n+1)/2],{n,20}]

FullSimplify[Subtract@@{Ceiling[((n^2)/(-1+2 n))],1+Floor[n/2]},n∈Integers&&n>0]

Table[-1+Ceiling[((n^2)/(-1+2 n))]-Floor[(n/2)],{n,20}]

CompleteTripartite k×m×n

*Not* Ceiling[((k m n)/(k+m+n-1))]

Flatten[Table[{{k,m,n},GraphData[{"CompleteTripartite",{k,m,n}},"Arboricity"],XXX},{n,10},{m,n},{k,m}],2]

Flatten[Monitor[Table[{{k,m,n},{Ceiling[((k m n)/(k+m+n-1))],Arboricity[System`CompleteGraph[{k,m,n}]]}},{n,5},{m,n},{k,m}],{k,m,n}],1]//Timing

CompleteTripartite n×n×n

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"Arboricity"],{n,10}]

Table[Arboricity[System`CompleteGraph[{n,n,n}]],{n,5}]//Timing

Crown

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

Monitor[Table[Arboricity[CrownGraph[n]],{n,3,9}],n]//Timing

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

CubeConnectedCycle

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

Monitor[Table[Arboricity[CubeConnectedCycleGraph[n]],{n,3,3}],n]//Timing

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

Cycle

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

Monitor[Table[Arboricity[System`CycleGraph[n]],{n,3,10}],n]//Timing

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

DiagonalIntersection

Table[GraphData[{"DiagonalIntersection",n},"Arboricity"],{n,3,14}]

Empty

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

Table[Arboricity[System`Graph[Range[n],{}]],{n,20}]//Timing

FibonacciCube

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

FoldedCube

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

Gear

Table[GraphData[{"Gear",n},"Arboricity"],{n,3,20}]

GeneralizedPetersen

Monitor[{g=#,Arboricity[GraphData[#]]}&/@SortBy[GraphData["GeneralizedPetersen",;;18],GraphData[#,"V"]&],g]//Column

OptionValue[GetGraphData,"IndexDirectory"]

FileNameJoin[{OptionValue[GetGraphData,"IndexDirectory"],"10.1","File.m"}]

Grid m×n

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

Monitor[Table[Arboricity[System`GridGraph[{n,n}]],{n,4},{m,n}],{m,n}]//Timing

Flatten[Table[{{m,n},GraphData[{"Grid",{m,n}},"Arboricity"],Piecewise[{{1,Min[m,n]==1}},2]},{n,10},{m,n}],1]

DeleteCases[%,{_,x_,x_}]

Grid n×n

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

Monitor[Table[Arboricity[System`GridGraph[{n,n}]],{n,4}],n]//Timing

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

Grid k×m×n

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

Probably 1 if any two are 1 and 2 otherwise

DeleteCases[Flatten[Table[{{k,m,n},GraphData[{"Grid",{k,m,n}}/.{1,x_,y_}:>{x,y},"Arboricity"],Piecewise[{{1,k==m==1||m==n==1||n==k==1}},2]},{n,10},{m,n},{k,m}],2],{_,x_,x_}|{_,_GraphData,_}]//Quiet

Grid n×n×n

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

Probably n

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

HalvedCube

Table[GraphData[{"HalvedCube",n},"Arboricity"],{n,10}]

Hanoi

Probably 2 (planar; so at most 3)

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

Helm

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

Hypercube

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

http://dl.acm.org/citation.cfm?id=916846

An investigation of hypercube invariants

Authors:Niall Michael Sylvester GrahamChairs:Frank HararyPublication:· Doctoral DissertationAn investigation of hypercube invariantsNew Mexico State University Las Cruces, NM, USA ©1989

Monitor[Table[Arboricity[HypercubeGraph[n]],{n,0,4}],n]//Timing

Table[Ceiling[(n+1)/2],{n,0,10}]

Keller

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

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

Monitor[Table[Arboricity[KellerGraph[n]],{n,2}],n]//Timing

King n×n

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

Knight m×n

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

Possibly 2 for Min[m,n] > 2

Block[{m,n},DeleteCases[{
{m,n}="Knight"/.GraphData[#,"NotationRules"],
GraphData[#,"Arboricity"],
Piecewise[{{1,Min[m,n]<3}},2]
}&/@GraphData["Knight"],{_,x_,x_}]]

Monitor[Table[Arboricity[KnightTourGraph[m,n]],{n,4},{m,n}],{m,n}]//Timing

Knight n×n

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

Possibly 2 for n > 2

Table[GraphData[{"Knight",{n,n}},"Arboricity"],{n,10}]

Monitor[Table[Arboricity[KnightTourGraph[n,n]],{n,4}],n]//Timing

Ladder

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

Monitor[Table[Arboricity[LadderGraph[n]],{n,8}],n]//Timing

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"Arboricity"],{n,3}]

MoebiusLadder

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

seq=Table[GraphData[{"MoebiusLadder",n},"Arboricity"],{n,3,25}]

Monitor[Table[Arboricity[MoebiusLadder[n]],{n,3,20}],n]//Timing

Mycielski

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

seq=Table[GraphData[{"Mycielski",n},"Arboricity"],{n,11}]

Monitor[Table[Arboricity[GraphData[{"Mycielski",n}]],{n,4}],n]//Timing

Odd

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

seq=Table[GraphData[{"Odd",n},"Arboricity"],{n,7}]

Monitor[Table[Arboricity[GraphData[{"Odd",n}]],{n,3}],n]//Timing

Pan

seq=Table[GraphData[{"Pan",n},"Arboricity"],{n,3,20}]

Path

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

seq=Table[GraphData[{"Path",n},"Arboricity"],{n,20}]

Monitor[Table[Arboricity[GraphData[{"Path",n}]],{n,10}],n]//Timing

PathComplement

seq=Table[GraphData[{"PathComplement",n},"Arboricity"],{n,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@Drop[seq,2],n-2],n∈Integers]

Table[(1/4) (2 n-3-(((-1))^n)),{n,20}]

Table[Piecewise[{{1,n==1||n==2}},Floor[((n-1)/2)]],{n,20}]

Table[Piecewise[{{1,n==1||n==2}},Ceiling[(n/2)]-1],{n,20}]

Prism

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

seq=Table[GraphData[{"Prism",n},"Arboricity"],{n,3,25}]

Monitor[Table[Arboricity[PrismGraph[n]],{n,3,8}],n]//Timing

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"Arboricity"],{n,10}]

Rook m×n

Probably Floor[(m+n)/2]

Block[{m,n},Sort@DeleteCases[{
{m,n}="Rook"/.GraphData[#,"NotationRules"],
GraphData[#,"Arboricity"],
Floor[(m+n)/2]
}&/@GraphData["Rook"],{_,x_,x_}]]

Rook n×n

Table[GraphData[{"Rook",{n,n}},"Arboricity"],{n,10}]

SierpinskiCarpet

Possibly 2

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

SierpinskiSieve

Possibly 2

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

SierpinskiTetrahedron

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

Star

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

Monitor[Table[Arboricity[System`StarGraph[n]],{n,17}],n]//Timing

Sun

Table[GraphData[{"Sun",n},"Arboricity"],{n,3,20}]

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

Sunlet

Table[GraphData[{"Sunlet",n},"Arboricity"],{n,3,20}]

Tetrahedral

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

Transposition

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

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

Monitor[Table[Arboricity[GraphData[{"Transposition",n}]],{n,3}],n]//Timing

Triangular

Table[GraphData[{"Triangular",n},"Arboricity"],{n,2,20}]

TriangularGrid

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

TriangularHoneycombAcuteKnight

Possibly 2 for n > 3

Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"Arboricity"],{n,20}]

TriangularHoneycombBishop

Table[GraphData[{"TriangularHoneycombBishop",n},"Arboricity"],{n,9}]

TriangularHoneycombObtuseKnight

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Arboricity"],{n,20}]

TriangularHoneycombQueen

Table[GraphData[{"TriangularHoneycombQueen",n},"Arboricity"],{n,10}]

TriangularHoneycombRook

Probably 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...

Table[GraphData[{"TriangularHoneycombRook",n},"Arboricity"],{n,10}]

Web

Table[GraphData[{"Web",n},"Arboricity"],{n,3,20}]

Wheel

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

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

SetProperty[#,VertexLabels->"Name"]&/@SpanningTrees[System`WheelGraph[4]]

{HighlightGraph[System`WheelGraph[4,VertexLabels->"Name"],UndirectedEdge@@@Partition[{4,1,3,2},2,1]],HighlightGraph[System`WheelGraph[4,VertexLabels->"Name"],UndirectedEdge@@@Partition[{1,2,4,3},2,1]]}

{HighlightGraph[System`WheelGraph[5,VertexLabels->"Name"],UndirectedEdge@@@Partition[{5,1,4,3,2},2,1]],HighlightGraph[System`WheelGraph[5,VertexLabels->"Name"],UndirectedEdge@@@Partition[{3,1,2,5,4},2,1]]}

Monitor[Table[Arboricity[System`WheelGraph[n]],{n,17}],n]//Timing

WhiteBishop n×n

Possibly 1, 2, 2, 3, 4, 4, 5, 6, 6, ...

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

Checks

DeleteCases[Monitor[{g=#,GraphData[#,"Arboricity"],Arboricity[GraphData[#]]}&/@GraphData[;;8],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,GraphData[#,"Arboricity"],Arboricity[GraphData[#],"Planar"->None]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,GraphData[#,"Arboricity"],Arboricity[GraphData[#],"Planar"->GraphData[#,"Planar"]]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing

Planar

The arboricity of a planar graph is at most 3 (Harary 1994, p. 124, Problem 11.22)

Select[GraphData["Planar"],IntegerQ[Υ=GraphData[#,"Arboricity"]]&&Υ>3&]

DeleteCases[Monitor[{g=#,GraphData[#,"Arboricity"],Arboricity[GraphData[#],"Planar"->None]}&/@GraphData["Planar",;;10],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,GraphData[#,"Arboricity"],Arboricity[GraphData[#],"Planar"->True]}&/@GraphData["Planar",;;10],g],{_,x_,x_}]//Timing

Algorithm

Incremental

ArboricityIncremental[g_System`Graph]:=Module[{e=EdgeList[g],a=1,acyc},
acyc=Select[Subsets[e],AcyclicGraphQ[System`Graph[#]]&];
While[Head[SelectFirst[Subsets[acyc,{a}],DuplicateFreeQ[Flatten[#]]&&Union@@#===e&]]===Missing,a++];
a]

DeleteCases[{#,GraphData[#,"Arboricity"],ArboricityIncremental[GraphData[#]]}&/@GraphData[;;5],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,GraphData[#,"Arboricity"],ArboricityIncremental[GraphData[#]]}&/@GraphData[;;6],g],{_,x_,x_}]//Timing

Graphs.m Subgraph

DeleteCases[Monitor[{g=#,GraphData[#,"Arboricity"],Arboricity[GraphData[#]]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing

Graphs.m MyFastSubgraph

DeleteCases[Monitor[{g=#,GraphData[#,"Arboricity"],Arboricity[GraphData[#]]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing

Using known Planar:

DeleteCases[Monitor[{g=#,GraphData[#,"Arboricity"],Arboricity[GraphData[#],"Planar"->GraphData[#,"Planar"]]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing