Extremal problems on cycles, packing, and decomposition of graphs

Wu, Hehui

Permalink

https://hdl.handle.net/2142/26227 Copy

Description

Title

Extremal problems on cycles, packing, and decomposition of graphs

Author(s)

Wu, Hehui

Issue Date

2011-08-25T22:19:34Z

Director of Research (if dissertation) or Advisor (if thesis)

West, Douglas B.

Doctoral Committee Chair(s)

Kostochka, Alexandr V.

Committee Member(s)

• West, Douglas B.
• Balogh, József
• Chekuri, Chandra S.

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2011-08

Permalink

http://hdl.handle.net/2142/26227

Copyright and License Information

Copyright 2011 by Hehui Wu. All rights reserved.

Owning Collections