Random subtrees of complete graphs

Authors Alex J. Chin, Gary Gordon, Kellie J. MacPhee, Charles Vincent

Publication date 21 August 2013

Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the asymptotic behavior of four statistics associated with subtrees of complete graphs: the uniform probability

p_{n}

that a random subtree is a spanning tree of

K_{n}

, the weighted probability

q_{n}

(where the probability a subtree is chosen is proportional to the number of edges in the subtree) that a random subtree spans and the two expectations associated with these two probabilities. We find

p_{n}

and

q_{n}

both approach

e^{- e^{- 1}} a p p r o x .692

, while both expectations approach the size of a spanning tree, i.e., a random subtree of

K_{n}

has approximately

n - 1

edges.

This page was built for publication: Random subtrees of complete graphs

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