Bounds on probability of connectedness of a random graph

Let G(V,E) be a connected graph with the vertex set V and set of edges E and M(E,T) its cyclic matroid. Acyclic subgraphs of G are the independent sets of the matroid M and spanning trees are the bases of M. The question of connectivity of a random graph (G,Q) obtained by random deleting edges of G is interpreted as determining a rank of a random matroid (M,Q) defined by random deleting of edges from M in the same way as in the graph G. By P(M,Q) is denoted the probability that a random subset of E includes a basis of the matroid M. The main result of this paper is an estimation of P(M,Q) in terms of the values of basic spectrum of the matroid M, defined by means of ranks of iterated sums of the matroid M. The probability P(M,Q) can be estimated as \(\prod^{r}_{i=1}(1- q^{\delta_ i})\leq P(M,Q)\) where q is a probability of deleting a single edge from G.

Recommendations

Cited in

(19)

This page was built for publication: Bounds on probability of connectedness of a random graph

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