Random graphs from a weighted minor-closed class

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.2701, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p52

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random graph core connectivity random cluster model minor-closed class

Mathematics Subject Classification ID

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

Abstract: There has been much recent interest in random graphs sampled uniformly from the n-vertex graphs in a suitable minor-closed class, such as the class of all planar graphs. Here we use combinatorial and probabilistic methods to investigate a more general model. We consider random graphs from a `well-behaved' class of graphs: examples of such classes include all minor-closed classes of graphs with 2-connected excluded minors (such as forests, series-parallel graphs and planar graphs), the class of graphs embeddable on any given surface, and the class of graphs with at most k vertex-disjoint cycles. Also, we give weights to edges and components to specify probabilities, so that our random graphs correspond to the random cluster model, appropriately conditioned. We find that earlier results extend naturally in both directions, to general well-behaved classes of graphs, and to the weighted framework, for example results concerning the probability of a random graph being connected; and we also give results on the 2-core which are new even for the uniform (unweighted) case.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Random graphs from a weighted minor-closed class

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