Files in this item
Files  Description  Format 

application/pdf Wu_Hehui.pdf (362Kb)  (no description provided) 
Description
Title:  Extremal problems on cycles, packing, and decomposition of graphs 
Author(s):  Wu, Hehui 
Director of Research:  West, Douglas B. 
Doctoral Committee Chair(s):  Kostochka, Alexandr V. 
Doctoral Committee Member(s):  West, Douglas B.; Balogh, József; Chekuri, Chandra S. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  graph
circumference Steiner tree packing Sconnector independent number connectivity decomposition fractional arborictiy. 
Abstract:  In this thesis, we study extremal problems concerning cycles and paths in graphs, graph packing, and graph decomposition. We use “graph” in the general sense, allowing loops and multiedges. The Chv´atal–Erd˝os Theorem states that every graph whose connectivity is at least its independence number has a spanning cycle. In 1976, Fouquet and Jolivet conjectured an extension: If G is an nvertex kconnected graph with independence number a, and a ≥ k, then G has a cycle with length at least k(n+a−k)/a . In Chapter 2 we prove this conjecture. NashWilliams and Tutte independently characterized when a graph has k edgedisjoint spanning trees; a consequence is that 2kedgeconnected graphs have k edgedisjoint spanning trees. Kriesell conjectured a more general statement: defining a set S ⊆ V (G) to be jedgeconnected in G if S lies in a single component of any graph obtained by deleting fewer than j edges from G, he conjectured that if S is 2kedgeconnected in G, then G has k edgedisjoint trees containing S. In Chapter 3, we show that it suffices for S to be 6.5kedgeconnected in G. A shortcutting operation on a graph G replaces a path in G by an edge joining its endpoints. An Sconnector of G is a subgraph of G from which after some shortcutting operations we get a connected graph with vertex set S. In Chapter 3, we also show that if S is 10kedgeconnected in G, then G has k edgedisjoint Sconnectors. Say that a graph with maximum degree at most d is dbounded. In chapter 4, we prove a sharp sparseness condition for decomposability into k forests plus one dbounded graph when d > k. Consequences are that every graph with fractional arboricity at most k + d/(k+d+1) has such a decomposition. When d = k +1, and also in the case where k = 1 and d ≤ 6, the dbounded graph in the decomposition can also equired to be a forest. For d ≤ k + 1, we prove that every graph with fractional arboricity at most k + d/(2k+2) decomposes into k forests plus one dbounded forest. 
Issue Date:  20110825 
URI:  http://hdl.handle.net/2142/26227 
Rights Information:  Copyright 2011 by Hehui Wu. All rights reserved. 
Date Available in IDEALS:  20110825 
Date Deposited:  201108 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics
Item Statistics
 Total Downloads: 226
 Downloads this Month: 19
 Downloads Today: 0