Densities of Minor-Closed Graph Families

Details Densities of Minor-Closed Graph Families Densities of Minor-Closed Graph Families

2010-09-28

arxiv.org/abs/1009.5633v1

Electronic J. Combinatorics 17(1), Paper R136, 2010

Mathematics

Combinatorics

19 pages, 4 figures

Scientific paper

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 {\omega}^{\omega}. 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).

Affiliated with

Also associated with

No associations

Rating

Densities of Minor-Closed Graph Families does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Densities of Minor-Closed Graph Families, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Densities of Minor-Closed Graph Families will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-694748