Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650425 | Discrete Mathematics | 2008 | 8 Pages |
Abstract
Given integers r and s, and n large compared to r and s, we determine the maximum size of a graph of order n having no minor isomorphic to sKrsKr, the union of s disjoint copies of KrKr.The extremal function depends on the relative sizes of r and s. If s is small compared to r the extremal function is essentially independent of s. On the other hand, if s is large compared to r , there is a unique extremal graph Ks(r-1)-1+K¯n-s(r-1)+1; this assertion is a generalization of the case r=3r=3 which is a classical result of Erdős and Pósa.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Andrew Thomason,