Extremal problems on cycles, packing, and decomposition of graphs

Graph;circumference;Steiner tree;packing S-connector;independent number;connectivity;decomposition;fractional arborictiy.

Wu, Hehui

关键词: Graph;    circumference;    Steiner tree;    packing S-connector;    independent number;    connectivity;    decomposition;    fractional arborictiy.;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/26227/Wu_Hehui.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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 itsindependence 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 spanningtrees. Kriesell conjectured a more general statement: defining a set S ⊆ V (G) to be j-edgeconnectedin 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 operationswe get a connected graph with vertex set S. In Chapter 3, we also show that if S is10k-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.