Hamiltonicity and Pancyclicity of 4-connected, Claw- and Net-freeGraphs Público

Gehrke, Silke (2009)

Permanent URL: https://etd.library.emory.edu/concern/etds/2227mq081?locale=es
Published

Abstract

Abstract Hamiltonicity and Pancyclicity of 4-connected, Claw- and Net-free Graphs By Silke Gehrke A well-known conjecture by Manton Matthews and David Sumner states that every 4-connected K1,3 -free graph is hamiltonian. The conjecture itself is still wide open, but several special cases have been shown so far. We will show results that support that conjecture. Especially, we will show that if a graph is 4-connected and {K1,3, N}- free, where N = N(i,j,k), with i + j + k = 5 and i, j, k 0, the graph is pancyclic.

Table of Contents

1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Basic Definitions and Notation . . . . . . . . . . . . . . . . . . 1 1.3 Background and Outline of Results . . . . . . . . . . . . . . . 4 2 Hamiltonicity of 4-connected, {K1,3, N(2, 2, 1)}-free or {K1,3, N(3, 1, 1)}-free graphs 8 2.1 Preliminary Lemmas . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Hamiltonicity of 4-connected, {K1,3, N}-free graphs, with N = N(2, 2, 1) or N = N(3, 1, 1) . . . . . . . . . . . . . . . . . . . 32 3 Hamiltonicity of 4-connected, {K1,3, N(3, 2, 0)}-free, {K1,3, N(4, 1, 0)}-free and {K1,3, N(5, 0, 0)}-free graphs 44 4 Pancyclicity 57 4.1 Preliminary Lemmas . . . . . . . . . . . . . . . . . . . . . . . 57 4.2 Pancyclicity of 4-connected, {K1,3, N}-free graphs . . . . . . . 75 4.3 Open questions and summary . . . . . . . . . . . . . . . . . . 92 Bibliography 94

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
Palabra Clave
Committee Chair / Thesis Advisor
Committee Members
Última modificación

Primary PDF

Thumbnail Title Date Uploaded Actions
Hamiltonicity and Pancyclicity of 4-connected, Claw- and Net-freeGraphs () 2018-08-28 13:03:37 -0400

Supplemental Files

Thumbnail Title Date Uploaded Actions
mydata.tex () 2018-08-28 13:04:37 -0400
preamble.tex () 2018-08-28 13:04:43 -0400