Semester
Fall
Date of Graduation
2001
Document Type
Dissertation
Degree Type
PhD
College
Eberly College of Arts and Sciences
Department
Mathematics
Committee Chair
Cun-Quan Zhang.
Abstract
This thesis is on a long standing open conjecture proposed by one of the most prominent mathematicians, Dr. C. Thomassen: Every longest circuit of 3-connected graph has a chord. In 1987, C. Q. Zhang proved that every longest circuit of a 3-connected planar graph G has a chord if G is cubic or if the minimum degree is at least 4. In 1997, Carsten Thomassen proved that every longest circuit of 3-connected cubic graph has a chord.;In this dissertation, we prove the following three independent partial results: (1) Every longest circuit of a 3-connected graph embedded in a projective plane with minimum degree at least has a chord (Theorem 2.3.1). (2) Every longest circuit of a 3-connected cubic graph has at least two chords. Furthermore if the graph is also a planar, then every longest circuit has at least three chords (Theorem 3.2.6, 3.2.7). (3) Every longest circuit of a 4-connected graph embedded in a torus or Klein bottle has a chord.;We get these three independent results with three totally different approaches: Connectivity (Tutte circuit), second Hamilton circuit, and charge and discharge methods.
Recommended Citation
Li, Xuechao, "Chords of longest circuits of graphs" (2001). Graduate Theses, Dissertations, and Problem Reports (ETD). 1450.
https://researchrepository.wvu.edu/etd/1450