Type of Document	Dissertation
Author	Wollan, Paul
Author's Email Address	wollan@math.gatech.edu
URN	etd-11232005-164743
Title	Extremal Functions for Graph Linkages and Rooted Minors
Degree	Doctor of Philosophy
Department	Mathematics
Advisory Committee	Advisor Name Title Robin Thomas Committee Chair Dana Randall Committee Member Richard Duke Committee Member William Trotter Committee Member Xingxing Yu Committee Member
Keywords	Graph Theory graph minors
Date of Defense	2005-11-11
Availability	unrestricted
Abstract 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.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    wollan_paul_200512_phd.pdf 753.12 Kb 00:03:29 00:01:47 00:01:34 00:00:47 00:00:04