Semester
Summer
Date of Graduation
2012
Document Type
Dissertation
Degree Type
PhD
College
Eberly College of Arts and Sciences
Department
Mathematics
Committee Chair
Cun-Quan Zhang.
Abstract
The research of my dissertation is motivated by the Circuit Double Cover Conjecture due to Szekeres and independently Seymour, that every bridgeless graph G has a family of circuits which covers every edge of G twice. By Fleischner's Splitting Lemma, it suffices to verify the circuit double cover conjecture for bridgeless cubic graphs.;It is well known that every edge-3-colorable cubic graph has a circuit double cover. The structures of edge-3-colorable cubic graphs have strong connections with the circuit double cover conjecture. In chapter two, we consider the structure properties of a special class of edge-3-colorable cubic graphs, which has an edge contained by a unique perfect matching. In chapter three, we prove that if a cubic graph G containing a subdivision of a special class of edge-3-colorable cubic graphs, semi-Kotzig graphs, then G has a circuit double cover.;Circuit extension is an approach posted by Seymour to attack the circuit double cover conjecture. But Fleischer and Kochol found counterexamples to this approach. In chapter four, we post a modified approach, called circuit extension sequence. If a cubic graph G has a circuit extension sequence, then G has a circuit double cover. We verify that all Fleischner's examples and Kochol's examples have a circuit extension sequence, and hence not counterexamples to our approach. Further, we prove that a circuit C of a bridgeless cubic G is extendable if the attachments of all odd Tutte-bridges appear on C consequently.;In the last chapter, we consider the properties of minimum counterexamples to the strong circuit double cover. Applying these properties, we show that if a cubic graph G has a long circuit with at least | V(G)| - 7 vertices, then G has a circuit double cover.
Recommended Citation
Ye, Dong, "Perfect Matching and Circuit Cover of Graphs" (2012). Graduate Theses, Dissertations, and Problem Reports. 3569.
https://researchrepository.wvu.edu/etd/3569
