Maximum degree in minor-closed classes of graphs

DOI10.1016/J.EJC.2016.02.001MaRDI QIDQ268260zbMATH OpenOpenAlexFDO

Authors Omer Giménez, D. Mitsche, Marc Noy

Publication date 14 April 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

maximum degree of random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Vertex degrees (05C07)

Abstract: Given a class of graphs G closed under taking minors, we study the maximum degree Delta_n of random graphs from G with n vertices. We prove several lower and upper bounds that hold with high probability. Among other results, we find classes of graphs providing orders of magnitude for Delta_n not observed before, such us log n/ log log log n and log n/ log log log log n.

Recommendations

• On the Maximum Degree of a Random Planar Graph
• The maximum degree of random planar graphs
• The maximum degree of series-parallel graphs
• The maximum degree of random planar graphs
• Random graphs from a minor-closed class

Cites work

• Degree distribution in random planar graphs
• Extremal Parameters in Sub-Critical Graph Classes
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs
• On the Maximum Degree of a Random Planar Graph
• On the maximum degree in a random tree
• Random graphs from a minor-closed class
• Random graphs with few disjoint cycles
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• The degree sequence of random graphs from subcritical classes
• The distribution of the maximum vertex degree in random planar maps
• The maximum degree in a random tree and related problems
• The maximum degree of random planar graphs
• The maximum degree of series-parallel graphs

Cited in

(8)

• Proper minor-closed families are small
• Phase transition of degeneracy in minor-closed families
• Random graphs from a block-stable class
• Exact-Size Sampling of Enriched Trees in Linear Time
• On the purity of minor-closed classes of graphs
• The maximal degree in a Poisson-Delaunay graph
• On the critical densities of minor-closed classes
• Modularity of minor‐free graphs

This page was built for publication: Maximum degree in minor-closed classes of graphs

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