On Cycles, Chorded Cycles, and Degree Conditions 公开

Keller, Ariel (Spring 2018)

Permanent URL: https://etd.library.emory.edu/concern/etds/qv33rw66f?locale=zh
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.

Table of Contents

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

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.
School
Department
Degree
Submission
Language
  • English
Research Field
关键词
Committee Chair / Thesis Advisor
Committee Members
最新修改

Primary PDF

Supplemental Files