Back to search

West Virginia University

Perfect Matching and Circuit Cover of Graphs

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
PhD
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematics

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ye, Dong

Subjects

dc:subject × 1

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ye, Dong. Perfect Matching and Circuit Cover of Graphs. Dissertation thesis, https://doi.org/10.33915/etd.3569