Random planar graphs with bounds on the maximum and minimum degrees

DOI10.1007/S00373-010-0960-7MaRDI QIDQ659667zbMATH OpenOpenAlexFDO

Authors Chris Dowden

Publication date 24 January 2012

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsrandom graphslabelled graphsbounded degrees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07)

Abstract: Let P_{n,d,D} denote the graph taken uniformly at random from the set of all labelled planar graphs on {1,2,...,n} with minimum degree at least d(n) and maximum degree at most D(n). We use counting arguments to investigate the probability that P_{n,d,D} wll contain given components and subgraphs, showing exactly when this is bounded away from 0 and 1 as n tends to infinity.

Recommendations

• The maximum degree of random planar graphs
• On the Maximum Degree of a Random Planar Graph
• Concentration of maximum degree in random planar graphs
• The maximum degree of random planar graphs
• Random planar graphs

Cites work

• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• Asymptotic enumeration and limit laws of planar graphs
• Random planar graphs
• Random planar graphs with \(n\) nodes and a fixed number of edges
• Subgraphs of 4-regular planar graphs
• The evolution of uniform random planar graphs

Cited in

(5)

• Random planar maps and graphs with minimum degree two and three
• Random graphs from a weighted minor-closed class
• The maximum and minimum degrees of random bipartite multigraphs
• Maximal planar subgraphs of fixed girth in random graphs
• Concentration of maximum degree in random planar graphs

This page was built for publication: Random planar graphs with bounds on the maximum and minimum degrees

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