کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653270 | 1632761 | 2016 | 7 صفحه PDF | دانلود رایگان |
A collection AA of graphs is called bridge-alterable if, for each graph GG with a bridge ee, GG is in AA if and only if G−eG−e is. For example the class FF of forests is bridge-alterable. For a random forest FnFn sampled uniformly from the set FnFn of forests on vertex set {1,…,n}{1,…,n}, a classical result of Rényi (1959) shows that the probability that FnFn is connected is e−12+o(1).Recently Addario-Berry et al. (2012) and Kang and Panagiotou (2013) independently proved that, given a bridge-alterable class AA, for a random graph RnRn sampled uniformly from the graphs in AA on {1,…,n}{1,…,n}, the probability that RnRn is connected is at least e−12+o(1). Here we give a more straightforward proof, and obtain a stronger non-asymptotic form of this result, which compares the probability to that for a random forest. We see that the probability that RnRn is connected is at least the minimum over 25n
Journal: European Journal of Combinatorics - Volume 56, August 2016, Pages 33–39