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 Attribution 4.0 International Public 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 Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View