3connected, Clawfree, Generalized Netfree graphs are Hamiltonian Open Access
Janiszewski, Susan Rae (2012)
Published
Abstract
Abstract
3connected, Clawfree, Generalized Netfree graphs are
Hamiltonian
Given a family F = {H1, H2, . . . , Hk} of graphs, we say that a
graph is
Ffree 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
3connected
graph is hamiltonian. First, we reduce the number of possible
forbidden
pairs by presenting families of graphs that are 3connected 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
3connected, {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 classiﬁcation 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 ClawFree, Ni,j,0free 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 ClawFree, N3,3,3free 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
 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 

Research field  
Keyword  
Committee Chair / Thesis Advisor  
Committee Members 
Primary PDF
Thumbnail  Title  Date Uploaded  Actions 

3connected, Clawfree, Generalized Netfree graphs are Hamiltonian ()  20180828 16:17:12 0400 

Supplemental Files
Thumbnail  Title  Date Uploaded  Actions 
