The number of graphs not containing K₃,3 as a minor

MaRDI QIDQ1010848zbMATH OpenFDO

Authors Stefanie Gerke, Omer Giménez, Marc Noy, Andreas Weißl

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/0803.4418, https://eudml.org/doc/129980, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r114.html

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

zbMATH Keywords

generating functionsnumber of labelled graphssymptotic estimates

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35)

Abstract: We derive precise asymptotic estimates for the number of labelled graphs not containing $K_{3,3}$ as a minor, and also for those which are edge maximal. Additionally, we establish limit laws for parameters in random $K_{3,3}$-minor-free graphs, like the expected number of edges. To establish these results, we translate a decomposition for the corresponding graph class into equations for generating functions and use singularity analysis. We also find a precise estimate for the number of graphs not containing the graph $K_{3,3}$ plus an edge as a minor.

Review text

Summary: We derive precise asymptotic estimates for the number of labelled graphs not containing \(K_{3,3}\) as a minor, and also for those which are edge maximal. Additionally, we establish limit laws for parameters in random \(K_{3,3}\)-minor-free graphs, like the number of edges. To establish these results, we translate a decomposition for the corresponding graphs into equations for generating functions and use singularity analysis. We also find a precise estimate for the number of graphs not containing the graph \(K_{3,3}\) plus an edge as a minor.

Recommendations

• Excluding a small minor
• Enumeration and limit laws for series-parallel graphs
• scientific article; zbMATH DE number 2192148
• The extremal function for noncomplete minors
• The structure and labelled enumeration of \(K_{3,3}\)-subdivision-free projective-planar graphs

Cited in

(4)

• Enumeration of labelled 4-regular planar graphs. II: Asymptotics
• Random graphs from a weighted minor-closed class
• On the probability of planarity of a random graph near the critical point
• Growth constants of minor-closed classes of graphs

This page was built for publication: The number of graphs not containing \(K_{3,3}\) as a minor

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