3-connected, Claw-free, Generalized Net-free graphs are Hamiltonian Open Access

Janiszewski, Susan Rae (2012)

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

Abstract

Abstract
3-connected, Claw-free, Generalized Net-free graphs are Hamiltonian
Given a family F = {H1, H2, . . . , Hk} of graphs, we say that a graph is
F-free if G contains no subgraph isomorphic to any Hi, i = 1, 2, . . . , k. The
graphs in the set F are known as forbidden subgraphs. In this work, we
continue to classify pairs of forbidden subgraphs that imply a 3-connected
graph is hamiltonian. First, we reduce the number of possible forbidden
pairs by presenting families of graphs that are 3-connected and not hamilto-
nian. Of particular interest is the graph K1,3, also known as the claw, as we
show that it must be included in any forbidden pair. Secondly, we let Ni,j,k
denote the generalized net, which is the graph obtained by rooting vertex-
disjoint paths of length i, j, and k at the vertices of a triangle. We show that
3-connected, {K1,3, Ni,j,0}-free graphs are hamiltonian for i, j = 0, i + j ≤ 9
and {K1,3, N3,3,3}-free graphs are hamiltonian. These results are best possi-
ble in the sense that no path of length i can be replaced by i + 1 in the above
net graphs. When combined with previously known results, this completes
the classification of generalized nets such that a graph being {K1,3, Ni,j,k}-
free implies hamiltonicity.

Table of Contents

1 Introduction 1
2 Background 6
3 Further Classification of Pairs of Forbidden Graphs 10
4 Claw-Free, Ni,j,0-free Graphs 16
4.1 Lemmas for the case that C is not dominating. . . . . . . . . . 18
4.2 Lemmas for the case that C is dominating. . . . . . . . . . . . 22
4.3 Proof of Theorem 4.1: T9,2,1 . . . . . . . . . . . . . . . . . . . 27
4.3.1 Case 1: C is not a dominating cycle. . . . . . . . . . . 27
4.3.2 Case 2a: C is a dominating cycle and c(G0) = 11. . . . 28
4.3.3 Case 2b: C is a dominating cycle and c(G0) = 10. . . . 29
4.3.4 Case 2c: C is a dominating cycle and c(G0) = 9. . . . . 30
4.4 Proof of Theorem 4.2: T8,3,1 . . . . . . . . . . . . . . . . . . . 32
4.4.1 Case 1: C is not a dominating cycle. . . . . . . . . . . 32
4.4.2 Case 2a: C is a dominating cycle and c(G0) = 11. . . . 33
4.4.3 Case 2b: C is a dominating cycle and c(G0) = 10. . . . 34
4.4.4 Case 2c: C is a dominating cycle and c(G0) = 9. . . . . 35
4.5 Proof of Theorem 4.3: T7,4,1 . . . . . . . . . . . . . . . . . . . 40
4.5.1 Case 1: C is not a dominating cycle. . . . . . . . . . . 40
4.5.2 Case 2a: C is a dominating cycle and c(G0) = 11. . . . 41
4.5.3 Case 2b: C is a dominating cycle and c(G0) = 10. . . . 42
4.5.4 Case 2c: C is a dominating cycle and c(G0) = 9. . . . . 44
4.6 Proof of Theorem 4.4: T6,5,1 . . . . . . . . . . . . . . . . . . . 48
4.6.1 Case 1: C is not a dominating cycle. . . . . . . . . . . 48
4.6.2 Case 2a: C is a dominating cycle and c(G0) = 11. . . . 49
4.6.3 Case 2b: C is a dominating cycle and c(G0) = 10. . . . 50
4.6.4 Case 2c: C is a dominating cycle and c(G0) = 9. . . . . 52
5 Claw-Free, N3,3,3-free Graphs 55
5.1 C is not a dominating cycle. . . . . . . . . . . . . . . . . . . . 56
5.1.1 Case 1: c(G0) ≥ 13. . . . . . . . . . . . . . . . . . . . . 59
5.1.2 Case 2: c(G0) = 12. . . . . . . . . . . . . . . . . . . . . 60
5.1.3 Case 3: c(G0) = 11. . . . . . . . . . . . . . . . . . . . . 61
5.1.4 Case 4: c(G0) = 10. . . . . . . . . . . . . . . . . . . . . 61
5.2 C is a dominating cycle. . . . . . . . . . . . . . . . . . . . . . 61
5.2.1 Case 1: c(G0) ≥ 12. . . . . . . . . . . . . . . . . . . . . 62
5.2.2 Case 2: c(G0) = 11. . . . . . . . . . . . . . . . . . . . . 65
5.2.3 Case 3: c(G0) = 10. . . . . . . . . . . . . . . . . . . . . 70
5.2.4 Case 4: c(G0) = 9. . . . . . . . . . . . . . . . . . . . . 77
6 Future Work 86

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
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files