Extremal Functions for Graph Linkages and Rooted Minors
Paul Wollan
137 pages
Directed by: Robin Thomas
A graph G is k-linked if for any 2k distinct vertices s_1,..., s_k,t_1,..., t_k there exist k vertex disjoint paths P_1,...,P_k such that the endpoints of P_i are s_i and t_i. Determining the
existence of graph linkages is a classic problem in graph theory with numerous applications. In this thesis, we examine sufficient conditions that guarantee a graph to be k-linked and give the following theorems.
(A) Every 2k-connected graph on n vertices with 5kn edges is k-linked.
(B) Every 6-connected graph on n vertices with 5n-14 edges is 3-linked.
The proof method for Theorem (A) can also be used
to give an elementary proof of the weaker bound that 8kn edges suffice. Theorem (A) improves upon the previously best known bound due to Bollobas and Thomason stating that 11kn edges suffice. The edge bound in Theorem (B) is optimal in that there exist 6-connected graphs on n vertices with 5n-15 edges that are not 3-linked.
The methods used prove Theorems (A) and (B) extend to a more general structure than graph linkages called rooted minors. We generalize the proof
methods for Theorems (A) and (B) to find edge bounds for general rooted minors, as well as finding the optimal edge bound for a specific
family of bipartite rooted minors.
We conclude with two graph theoretical applications of graph linkages. The first is to the problem of determining when a small number of vertices can be used to cover all the odd cycles in a graph. The second is a simpler proof of a result of Boehme, Maharry and Mohar on complete
minors in huge graphs of bounded tree-width.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/7552 |
| Date | 28 November 2005 |
| Creators | Wollan, Paul |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
| Format | 753124 bytes, application/pdf |
Page generated in 0.007 seconds