Random graphs from a weighted minor-closed class

zbMATH Open1295.05212arXiv1210.2701MaRDI QIDQ396764FDOQ396764

Authors: Colin McDiarmid 

Publication date: 14 August 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1210.2701

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

Recommendations

• Random graphs from a minor-closed class
• Connectivity for random graphs from a weighted bridge-addable class
• Asymptotic Properties of Some Minor-Closed Classes of Graphs
• Asymptotic properties of some minor-closed classes of graphs
• On random graphs from a minor-closed class

zbMATH Keywords

random graphcoreconnectivityrandom cluster modelminor-closed class

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Title not available (Why is that?)
• Analytic combinatorics
• Title not available (Why is that?)
• A course in combinatorics.
• A complete grammar for decomposing a family of graphs into 3-connected components
• Enumeration and limit laws for series-parallel graphs
• Two critical periods in the evolution of random planar graphs
• Vertices of given degree in series-parallel graphs
• Asymptotic enumeration and limit laws of planar graphs
• Asymptotic study of subcritical graph classes
• Random cubic planar graphs
• The degree sequence of random graphs from subcritical classes
• The maximum degree of series-parallel graphs
• Title not available (Why is that?)
• Percolation and the hard-core lattice gas model
• Homomorphiesätze für Graphen
• Random graphs.
• The Random-Cluster Model
• Random graphs with few disjoint cycles
• On the Maximum Degree of a Random Planar Graph
• Random graphs from a minor-closed class
• Degree distribution in random planar graphs
• Random planar graphs
• Connectivity for random graphs from a weighted bridge-addable class
• Title not available (Why is that?)
• Graph minors. I. Excluding a forest
• Proper minor-closed families are small
• The number of labeled 2-connected planar graphs
• Asymptotic enumeration and limit laws for graphs of fixed genus
• On the degree distribution of random planar graphs
• Random graphs on surfaces
• On the diameter of random planar graphs
• Boltzmann Samplers, Pólya Theory, and Cycle Pointing
• Coefficients of functional compositions often grow smoothly
• The number of graphs not containing \(K_{3,3}\) as a minor
• The enumeration of planar graphs via Wick's theorem
• The evolution of uniform random planar graphs
• Random planar graphs with \(n\) nodes and a fixed number of edges
• Maximal biconnected subgraphs of random planar graphs
• 3-Connected Cores In Random Planar Graphs
• Uniform random sampling of planar graphs in linear time
• Random unlabelled graphs containing few disjoint cycles
• Random planar graphs with given average degree
• Graph classes with given 3-connected components: asymptotic counting and critical phenomena
• On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs
• On the number of series parallel and outerplanar graphs
• Title not available (Why is that?)
• Counting planar graphs and related families of graphs
• Asymptotics for logical limit laws: When the growth of the components is in an RT class
• Title not available (Why is that?)
• On the Number of Edges in Random Planar Graphs
• Random graphs containing few disjoint excluded minors
• The maximum degree of random planar graphs
• Asymptotic enumeration of labelled graphs by genus
• On graphs with few disjoint \(t\)-star minors
• Random planar graphs with bounds on the maximum and minimum degrees
• Small graph classes and bounded expansion
• Growth constants of minor-closed classes of graphs

Cited In (6)

• Pendant appearances and components in random graphs from structured classes
• Bridge-addability, edge-expansion and connectivity
• Random graphs from a minor-closed class
• Random walks and forbidden minors II
• Asymptotic properties of some minor-closed classes of graphs
• Local convergence of random planar graphs

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)