scientific article; zbMATH DE number 19179

MaRDI QIDQ3976607zbMATH OpenFDO

Authors Zhi-Hong Chen, Paul A. Catlin

Publication date 26 June 1992

zbMATH Keywords

arboricityedge-disjoint spanning treesrandom graph

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Random graphs (graph-theoretic aspects) (05C80)

Review text

[For the entire collectin see Zbl 0734.00014.] If \(G\) is the random graph, then the authors show that the expression \(| E(H)|/(| V(H)|-1)\) in the formula for arboricity given by \(a(G)=\max_{H\subseteq G}\left\lceil{| E(H)|\over | V(H)|-1}\right\rceil\) attains its maximum if and only if \(H=G\). They also obtain the maximum number of edge-disjoint spanning trees in the random graph \(G\). For the entire collection see [Zbl 0751.05025].

Recommendations

• scientific article; zbMATH DE number 866660
• Publication:4863468
• Arboricity and spanning‐tree packing in random graphs

Cited in

(5)

• Linear arboricity of random regular graphs
• Arboricity and spanning‐tree packing in random graphs
• scientific article; zbMATH DE number 841622 (Why is no real title available?)
• scientific article; zbMATH DE number 866660 (Why is no real title available?)
• Arboricity and spanning-tree packing in random graphs with an application to load balancing

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976607)