2026-09-20T09:34:56Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/26227 2023-07-10 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

West, Douglas B. Kostochka, Alexandr V. West, Douglas B. Balogh, József Chekuri, Chandra S. Wu, Hehui 2011-08-25T22:19:34Z 2011-08-25T22:19:34Z 2011-08-25T22:19:34Z 2011-08 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. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-06-24T20:04:43Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 3 Wu_Hehui.tex: 218001 bytes, checksum: 2c9d2fbee021eb45b7c25352fd8e08e5 (MD5) Wu_Hehui.pdf: 585060 bytes, checksum: 73c226e5afbc746c9d7d287b0ac6bb49 (MD5) Wu_Hehui.pdf: 361930 bytes, checksum: 893b82fdcd3492904c122f4855c3c171 (MD5) Made available in DSpace on 2011-08-25T22:19:34Z (GMT). No. of bitstreams: 3 Wu_Hehui.pdf: 361919 bytes, checksum: b72b5a64304fc10694d796e46ce67345 (MD5) Wu_Hehui.tex: 217987 bytes, checksum: f31a62aed8e531d7cb15c5eecbb4faa8 (MD5) license.txt: 4058 bytes, checksum: ccabcf556f10956ba71ae443594f28d1 (MD5) http://hdl.handle.net/2142/26227 en Copyright 2011 by Hehui Wu. All rights reserved. Graph circumference Steiner tree packing S-connector independent number connectivity decomposition fractional arborictiy. Extremal problems on cycles, packing, and decomposition of graphs Mathematics 1257 Mathematics 0439 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Mathematics -UIUC 10KS0439PHD