Show simple item record

dc.contributor.authorWollan, Paulen_US
dc.date.accessioned2006-01-18T22:22:48Z
dc.date.available2006-01-18T22:22:48Z
dc.date.issued2005-11-28en_US
dc.identifier.urihttp://hdl.handle.net/1853/7552
dc.description.abstractExtremal 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.en_US
dc.format.extent753124 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectGraph theoryen_US
dc.subjectGraph minors
dc.subject.lcshExtremal problems (Mathematics)en_US
dc.subject.lcshGraph theoryen_US
dc.titleExtremal Functions for Graph Linkages and Rooted Minorsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentMathematicsen_US
dc.description.advisorCommittee Chair: Robin Thomas; Committee Member: Dana Randall; Committee Member: Richard Duke; Committee Member: William Trotter; Committee Member: Xingxing Yuen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record