Date of Award
Ph.D. in Mathematics
Talmage J. Reid
University of Mississippi
Interest in the cardinality of the intersection of two longest cycles is inspired by Scott Smith, who conjectured that in a k-connected graph, two longest cycles meet in at least k vertices. Grőtschel and Nemhauser, Grőtschel, and Stewart and Thompson proved Smith’s Conjecture for 2 ≤ k ≤ 8, and for general k, Chen, Faudree, and Gould proved that in a k-connected graph, two longest cycles meet in at least c0k3/5 vertices, where c0 ≈ 0.2615. In this dissertation, we study the intersection of two long cycles or two long paths passing through a specified linear forest subgraph in which each component is a path or empty set.
Let G be a k-connected graph (k ≥ 2), F be a linear forest subgraph of G with at most k − 1 vertices, and cF (G) be the length of a longest cycle containing F. We pose a more general conjecture than Smith’s Conjecture which states that if C and D are cycles of a k-connected graph G containing F such that |C| + |D| ≥ 2cF (G) − 1, then C and D must meet in at least k common vertices. In Chapter 3, we prove this conjecture for 2 ≤ k ≤ 6. In Chapter 4, we extend Chen, Faudree, and Gould’s result and give a lower bound for the intersection of two long cycles in a k-connected graph. In Chapter 5, we give a lower bound on the intersection of two long cycles containing a linear forest in a k-connected graph. Finally, in Chapter 6, as consequences of the main theorems regarding cycles, we provide analogous path results.
Kains, Philip, "On Intersections of Long Cycles and Paths in k-Connected Graphs" (2023). Electronic Theses and Dissertations. 2690.
Available for download on Saturday, April 06, 2024