{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/26227"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/26227","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Extremal problems on cycles, packing, and decomposition of graphs","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Wu, Hehui"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B.","Kostochka, Alexandr V.","Balogh, József","Chekuri, Chandra S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-08-25T22:19:34Z","date_published":"2011-08-25T22:19:34Z","updated_at":"2026-07-22T22:25:26Z","subjects":["Graph","circumference","Steiner tree","packing S-connector","independent number","connectivity","decomposition","fractional arborictiy."],"languages":["en"],"rights":["Copyright 2011 by Hehui Wu. All rights reserved."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/26227","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B.","Kostochka, Alexandr V.","Balogh, József","Chekuri, Chandra S."]},{"key":"dc:creator","label":"Author","values":["Wu, Hehui"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-08-25T22:19:34Z","2011-08"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph","circumference","Steiner tree","packing S-connector","independent number","connectivity","decomposition","fractional arborictiy."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 by Hehui Wu. All rights reserved."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/26227"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)"]},{"key":"dc:title","label":"Title","values":["Extremal problems on cycles, packing, and decomposition of graphs"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B.","Kostochka, Alexandr V.","Balogh, József","Chekuri, Chandra S."],"dc:creator":["Wu, Hehui"],"dc:date":["2011-08-25T22:19:34Z","2011-08"],"dc:description":["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)"],"dc:identifier":["http://hdl.handle.net/2142/26227"],"dc:language":["en"],"dc:rights":["Copyright 2011 by Hehui Wu. All rights reserved."],"dc:subject":["Graph","circumference","Steiner tree","packing S-connector","independent number","connectivity","decomposition","fractional arborictiy."],"dc:title":["Extremal problems on cycles, packing, and decomposition of graphs"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:26Z"}