Electronic Theses and Dissertations

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.

Available for download on Saturday, April 06, 2024

Share

COinS