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

Densities of Minor-Closed Graph Families

  • Author(s): Eppstein, David
  • et al.
Creative Commons 'BY' version 4.0 license
Abstract

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
Current View