On Cycles, Chorded Cycles, and Degree Conditions 公开

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	Laney Graduate School
Department	Mathematics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Mathematics
关键词	cycles degree sum chorded cycles
Committee Chair / Thesis Advisor	Gould, Ronald J., Emory University
Committee Members	Duffus, Dwight, Emory University Huang, Hao, Emory University Rodl, Vojtech, Emory University

最新修改

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	On Cycles, Chorded Cycles, and Degree Conditions ()	2018-04-06 00:29:28 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions