Date of Award
1-1-2023
Document Type
Dissertation
Degree Name
Ph.D. in Mathematics
First Advisor
Haidong Wu
Second Advisor
Talmage J. Reid
Third Advisor
Bing Wei
School
University of Mississippi
Relational Format
dissertation/thesis
Abstract
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.
Recommended Citation
Kains, Philip, "On Intersections of Long Cycles and Paths in k-Connected Graphs" (2023). Electronic Theses and Dissertations. 2690.
https://egrove.olemiss.edu/etd/2690