Abstract
dc:description.abstractIn this dissertation, a problem related to Hadwiger's conjecture has been studied. We first proved a conjecture of Jakobsen from 1983 which states that every simple graphs on $n$ vertices and at least (11n-35)/2 edges either has a minor isomorphic to K_8 with one edge deleted or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2} and/or K_7 by identifying cliques of size five. We then studied the extremal functions for complete minors. We proved that every simple graph on nge9 vertices and at least 7n-27 edges either has a minor, or is isomorphic to K_{2, 2, 2, 3, 3}, or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2, 2} by identifying cliques of size six. This result extends Mader's theorem on the extremal function for K_p minors, where ple7. We discussed the possibilities of extending our methods to K_{10} and K_{11} minors. We have also found the extremal function for K_7 plus a vertex minor.
Degree
thesis:*- Department dc:contributor.department
- Algorithms, Combinatorics, and Optimization
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2004
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Song, Zixia
- Advisor dc:contributor.advisor
-
- Thomas, Robin
- Committee members dc:contributor.committeemember
-
- Richard Duke
- Robert G. Parker
- Anurag Singh
- William T. Trotter
Subjects
dc:subject × 8Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/6425