Concentration of maximum degree in random planar graphs

DOI10.1016/j.jctb.2022.05.005zbMath1495.05315arXiv2104.14790OpenAlexW3157980792MaRDI QIDQ2673490

Mihyun Kang, Michael Missethan

Publication date: 10 June 2022

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

random graphsmaximum degreeballs into binsrandom planar graphsPrüfer sequence

Mathematics Subject Classification ID

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

Related Items

The mesoscopic geometry of sparse random maps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Degree distribution in random planar graphs
• Random graphs on surfaces
• The distribution of the maximum degree of a random graph
• Degree sequences of random graphs
• On the chromatic index of almost all graphs
• Random planar graphs
• Pattern occurrences in random planar maps
• Asymptotic enumeration and limit laws for graphs of fixed genus
• On the maximum degree in a random tree
• The Maximum Degree of a Random Graph
• Two critical periods in the evolution of random planar graphs
• The maximum degree of random planar graphs
• Maximal biconnected subgraphs of random planar graphs
• 3-Connected Cores In Random Planar Graphs
• Uniform random sampling of planar graphs in linear time
• Asymptotic enumeration and limit laws of planar graphs
• On the Maximum Degree of a Random Planar Graph
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Vertices of given degree in a random graph
• On the Asymptotic Behavior of Degrees of Vertices in a Random Graph
• The Structure of a Random Graph at the Point of the Phase Transition
• The maximum degree in a random tree and related problems
• The degree sequence of a random graph. I. The models
• The Evolution of Random Graphs on Surfaces
• Paths in graphs
• On the Number of Edges in Random Planar Graphs
• Further results on random cubic planar graphs
• Phase transitions in graphs on orientable surfaces
• Limit laws of planar maps with prescribed vertex degrees
• The birth of the giant component
• On the Diameter of Random Planar Graphs
• The random planar graph process
• On the probability of planarity of a random graph near the critical point
• Longest and shortest cycles in random planar graphs