Semester
Spring
Date of Graduation
2023
Document Type
Dissertation
Degree Type
PhD
College
Eberly College of Arts and Sciences
Department
Mathematics
Committee Chair
Kevin Milans
Committee Member
John Goldwasser
Committee Member
Hong-Jian Lai
Committee Member
Jerzy Wojciechowski
Committee Member
Xi Yu
Abstract
A longest path transversal in a graph G is a set of vertices S of G such that every longest path in G has a vertex in S. The longest path transversal number of a graph G is the size of a smallest longest path transversal in G and is denoted lpt(G). Similarly, a longest cycle transversal is a set of vertices S in a graph G such that every longest cycle in G has a vertex in S. The longest cycle transversal number of a graph G is the size of a smallest longest cycle transversal in G and is denoted lct(G). A Gallai family is a family of graphs whose connected members have longest path transversal number 1. In this paper we find several Gallai families and give upper bounds on lpt(G) and lct(G) for general graphs and chordal graphs in terms of |V(G)|.
Recommended Citation
Long, James A. Jr, "Longest Path and Cycle Transversal and Gallai Families" (2023). Graduate Theses, Dissertations, and Problem Reports. 11784.
https://researchrepository.wvu.edu/etd/11784