Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650432 | Discrete Mathematics | 2008 | 11 Pages |
Abstract
Let D(H)D(H) be the minimum d such that every graph G with average degree d has an H -minor. Myers and Thomason found good bounds on D(H)D(H) for almost all graphs H and proved that for ‘balanced’ H random graphs provide extremal examples and determine the extremal function. Examples of ‘unbalanced graphs’ are complete bipartite graphs Ks,tKs,t for a fixed s and large t . Myers proved upper bounds on D(Ks,t)D(Ks,t) and made a conjecture on the order of magnitude of D(Ks,t)D(Ks,t) for a fixed s and t→∞t→∞. He also found exact values for D(K2,t)D(K2,t) for an infinite series of t. In this paper, we confirm the conjecture of Myers and find asymptotically (in s ) exact bounds on D(Ks,t)D(Ks,t) for a fixed s and large t.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Alexandr Kostochka, Noah Prince,