Random planar graphs with bounds on the maximum and minimum degrees

DOI10.1007/S00373-010-0960-7zbMATH Open1234.05207arXiv1101.5288OpenAlexW3102272889MaRDI QIDQ659667FDOQ659667

Authors: Chris Dowden 

Publication date: 24 January 2012

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

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.

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

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

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)

Cites Work

• Asymptotic enumeration and limit laws of planar graphs
• Title not available (Why is that?)
• Random planar graphs
• The evolution of uniform random planar graphs
• Random planar graphs with \(n\) nodes and a fixed number of edges
• Subgraphs of 4-regular planar graphs

Cited In (6)

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

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)