3-connected, Claw-free, Generalized Net-free graphs are Hamiltonian Public
Janiszewski, Susan Rae (2012)
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
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Mot-clé | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
|
3-connected, Claw-free, Generalized Net-free graphs are Hamiltonian () | 2018-08-28 16:17:12 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|