IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Extremal problems on cycles, packing, and decomposition of graphs

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/26227

Files in this item

File Description Format
PDF Wu_Hehui.pdf (362KB) (no description provided) PDF
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 Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(s): graph circumference Steiner tree packing S-connector 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 multi-edges. 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 n-vertex k-connected 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. Nash-Williams and Tutte independently characterized when a graph has k edge-disjoint spanning trees; a consequence is that 2k-edge-connected graphs have k edge-disjoint spanning trees. Kriesell conjectured a more general statement: defining a set S ⊆ V (G) to be j-edgeconnected 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 2k-edge-connected in G, then G has k edge-disjoint trees containing S. In Chapter 3, we show that it suffices for S to be 6.5k-edge-connected in G. A shortcutting operation on a graph G replaces a path in G by an edge joining its endpoints. An S-connector 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 10k-edge-connected in G, then G has k edge-disjoint S-connectors. Say that a graph with maximum degree at most d is d-bounded. In chapter 4, we prove a sharp sparseness condition for decomposability into k forests plus one d-bounded 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 d-bounded 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 d-bounded forest.
Issue Date: 2011-08-25
URI: http://hdl.handle.net/2142/26227
Rights Information: Copyright 2011 by Hehui Wu. All rights reserved.
Date Available in IDEALS: 2011-08-25
Date Deposited: 2011-08
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 161
  • Downloads this Month: 3
  • Downloads Today: 0

Browse

My Account

Information

Access Key