Balanced Extensions of Spare Graphs

Authors:

• Tomasz Łuczak,
• Andrzej Ruciński

Abstract

Let d(H) be the ratio of the number of edges to the number of vertices of a graph H and let d^*(H) be obtained from d(H) by decreasing the denominator by 1. Furthermore, let m(G) = max/HCG d(H) and m^*(G) = max/HCG d^*(H). We prove that there are numbers no and C such that for every graph G with n ≥ n₀ vertices and 1 >m(G) < 10/9 [m(G) 4.25] there is a supergraph F with at most C_n/(m(G)- 1) [203n] vertices such that m(F) = d(F) = m(G) and we also prove a similar result for m^*(G). The former partially solves a problem raised by Erdös. The latter can be reformulated as follows: for every graph G with n ≥ n₀ vertices and m^*(G) = p/q, p and q integers, 1

4.25], the smallest graph which contains G and whose edge set can be covered by p spanning trees so that each edge belongs to precisely q of them has at most Cn/(m^*(G)- 1) [203_n] vertices. Our method involves random graphs and therefore is nonconstructive. © 1992, Academic Press, Inc. All rights reserved.