Skip to main content
Open Access Publications from the University of California

UC Irvine

UC Irvine Previously Published Works bannerUC Irvine

Densities of Minor-Closed Graph Families

Creative Commons 'BY' version 4.0 license

We define the limiting density of a minor-closed family of simple graphs F to be the smallest number k such that every n-vertex graph in F has at most kn(1 + o(1)) edges, and we investigate the set of numbers that can be limiting densities. This set of numbers is countable, well-ordered, and closed; its order type is at least w(w). It is the closure of the set of densities of density-minimal graphs, graphs for which no minor has a greater ratio of edges to vertices. By analyzing density-minimal graphs of low densities, we find all limiting densities up to the first two cluster points of the set of limiting densities, 1 and 3/2. For multigraphs, the only possible limiting densities are the integers and the superparticular ratios i/(i + 1).

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View