When bad things happen to good trees*
Manuel Aivaliotis, Gary Gordon, William Graveman · Journal of Graph Theory · 2001
Abstract When the edges in a tree or rooted tree fail with a certain fixed probability, the (greedoid) rank may drop. We compute the expected rank as a polynomial in p and as a real number under the assumption of uniform distribution. We obtain several different expressions for this expected rank polynomial for both trees and rooted trees, one of which is especially simple in each case. We also prove two extremal theorems that determine both the largest and smallest values for the expected rank of a (rooted or unrooted) tree, and precisely when these extreme bounds are achieved. We conclude with directions for further study. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 79–99, 2001