On Chorded Cycles Open Access

Cream, Megan (2015)

Permanent URL: https://etd.library.emory.edu/concern/etds/h128nf499?locale=en


Historically, there have been many results concerning sufficient conditions for implying certain sets of cycles in graphs. My thesis aims to extend many of these well known results to similar results on sets of chorded (and sometimes even doubly chorded) cycles. In particular, we consider minimum degree, delta(G) and a Ore-type degree sum condition, sigma_2(G) of a graph G, sufficient to guarantee the existence of k vertex disjoint chorded cycles often containing specified elements of the graph, such as certain vertices or edges. Further, we extend a result on vertex disjoint cycles and chorded cycles to an analogous result on vertex disjoint cycles and doubly chorded cycles. We define a new graph property called chorded pancyclicity, and investigate a density condition and forbidden subgraphs in claw-free graphs that imply this new property. Specifically, we forbid certain paths and triangles with pendant paths. This is joint work with Dongqin Cheng, Ralph Faudree, Ron Gould, and Kazuhide Hirohata.

Table of Contents

1 Introduction (p.1)

1.1 History (p.1)

1.2 Some Basics (Definitions and Notation) (p.3)

1.3 Known Results for Sets of Cycles Containing Specified Graph Elements (p.5)

1.4 Known Results for Vertex Disjoint Cycles and Chorded Cycles (p.6)

1.5 Known Results for Pancyclic Graphs (p.7)

2 Vertex Disjoing Chorded Cycles Containing Specified Graph Elements (p.10)

2.1 Introduction (p.10)

2.2 Results (p.12)

2.2.1 Placing Edges as Chords on Cycles (p.12)

2.2.2 Placing Edges on Chorded Cycles (p.24)

2.2.3 Placing Vertices on Chorded Cycles (p.31)

3 A Result on Vertex Disjoint Cycles and Doubly Chorded Cycles (p.42)

3.1 Introduction (p.42)

3.2 Some Lemmas (p.45)

3.3 Proof of Theorem 3.6 (p.48)

4 Forbidden Subgraphs for Chorded Pancyclicity (p.56)

4.1 Introduction (p.56)

4.2 Results (p.58)

4.2.1 Introduction to Chorded Pancyclicity (p.58)

4.2.2 Edge Density and Chorded Pancyclicity (p.59)

4.2.3 Forbidden Subgraphs (p.61)

Bibliography (p.75)

About this Dissertation

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
  • English
Research Field
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files