Electronic Theses and Dissertations

Date of Award


Document Type


Degree Name

Ph.D. in Mathematics

First Advisor

Haidong Wu

Second Advisor

Talmage J. Reid

Third Advisor

Bing Wei


University of Mississippi

Relational Format



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.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.