# On Cycles, Chorded Cycles, and Degree Conditions Open Access

## Keller, Ariel (Spring 2018)

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

## Abstract

Sufficient conditions to imply the existence of certain substructures in a graph are of considerable interest in extremal graph theory, and conditions that guarantee a large set of cycles or chorded cycles are a recurring theme. This dissertation explores different degree sum conditions that are sufficient for finding a large set of vertex-disjoint cycles or a large set of vertex-disjoint chorded cycles in a graph. For an integer t >= 1, let sigma_t (G) be the smallest sum of degrees of t independent vertices of G. We first prove that if a graph G has order at least 7k+1 and degree sum condition sigma_4(G) >= 8k-3, with k >= 2, then G contains k vertex-disjoint cycles. Then, we consider an equivalent condition for chorded cycles, proving that if G has order at least 11k+7 and sigma_4(G) >= 12k-3, with k >= 2, then G contains k vertex-disjoint chorded cycles. We prove that the degree sum condition in each result is sharp. Finally, we conjecture generalized degree sum conditions on sigma_t(G) for t >= 2 sufficient to imply that G contains k vertex-disjoint cycles for k >= 2 and k vertex-disjoint chorded cycles for k >= 2. This is joint work with Ronald J. Gould and Kazuhide Hirohata.

Chapter 1: Introduction 1 1.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Definitions and Notation . . . . . . . . . . . . . . . . . . . . . . 4

Chapter 2: Degree Conditions to Imply the Existence of Vertex-Disjoint Cycles 7 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Proof of Theorem 2.1 . . . . . . . . . . . . . . . . . . . . . . . . .11 2.4 Proofs of Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.1 Proof of Lemma 2.1 . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.2 Proof of Lemma 2.5 . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.3 Proof of Lemma 2.6 . . . . . . . . . . . . . . . . . . . . . . . . 33

Chapter 3: Degree Conditions to Imply the Existence of Vertex-Disjoint Chorded Cycles 35 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  37 3.3 Proof of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . .  46

Bibliography 72