3-connected, Claw-free, Generalized Net-free graphs are Hamiltonian Pubblico

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	Laney Graduate School
Department	Math and Computer Science
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Mathematics
Parola chiave	hamiltonian, forbidden subgraphs, claw-free
Committee Chair / Thesis Advisor	Gould, Ronald J, Emory University
Committee Members	Rodl, Vojtech, Emory University Duffus, Dwight A, Emory University

Ultima modifica

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	3-connected, Claw-free, Generalized Net-free graphs are Hamiltonian ()	2018-08-28 16:17:12 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions