Premium
Arboricity and spanning‐tree packing in random graphs
Author(s) -
Gao Pu,
PérezGiménez Xavier,
Sato Cristiane M.
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20743
Subject(s) - arboricity , combinatorics , mathematics , random graph , graph , disjoint sets , spanning tree , minimum spanning tree , degeneracy (biology) , discrete mathematics , enhanced data rates for gsm evolution , computer science , planar graph , bioinformatics , telecommunications , biology
We study the arboricity A and the maximum number T of edge‐disjoint spanning trees of the classical random graph G ( n , p ) . For all p ( n ) ∈ [ 0 , 1 ] , we show that, with high probability, T is precisely the minimum of δ and⌊ m / ( n − 1 ) ⌋ , where δ is the minimum degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that the following holds. Above this threshold, T equals⌊ m / ( n − 1 ) ⌋and A equals⌈ m / ( n − 1 ) ⌉ . Below this threshold, T equals δ , and we give a two‐value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are randomly added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two‐choice load balancing problem, where k → ∞ .