On the Number of Edges in 2-factor Isomorphic Graphs Público
Wrayno, Paul Michael (2011)
Published
Abstract
Abstract
On the Number of Edges in 2-factor Isomorphic Graphs
By Paul M. Wrayno
A 2-factor is a collection of disjoint cycles in a graph that cover
all vertices
of that graph. A graph is called 2-factor isomorphic if all of its
2-factors are
the same when viewed as a multiset of unlabeled cycles.
In this dissertation, we find the maximum size of 2-factor
isomorphic
graphs that contain a desired 2-factor. We are also able to give
general
bounds when no 2-factor is specified or any 2-factor with a
fixed number of
cycles is desired. We also find similar results for the
special case where the
underlying graph is bipartite. In each case we provide
constructions that
attain the maximum size.
On the Number of Edges in 2-factor Isomorphic Graphs
By
Paul M. Wrayno
Ph.D., Emory University, 2011
Advisor: Ronald Gould, Ph.D.
A dissertation submitted to the Faculty of the
James T. Laney School of Graduate Studies of Emory University
in partial fulfillment of the requirements of the degree
of
Doctor of Philosophy
in Mathematics
2011
Table of Contents
1 Introduction 1
1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Hamiltonian Results that Lead to 2-Factor Results . . . . . 5
1.3 2-Factor Hamiltonian and 2-factor Isomorphic Graphs . . 7
2 Bipartite Graphs 9
2.1 Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Small Hamiltonian Constructions . . . . . . . . . . . . . . . 10
2.1.2 Larger Hamiltonian Constructions . . . . . . . . . . . . . . 10
2.1.3 General Construction . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Bounding the Size in Bipartite 2-factor Isomorphic
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Bound for Chords of Cycles in F and Edges on Cycles
in F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 Bound for Edges Between Cycles . . . . . . . . . . . . . . 16
2.2.3 Combining the Bounds . . . . . . . . . . . . . . . . . . . . . 17
2.3 Sharpness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Extensions to unknown F . . . . . . . . . . . . . . . . . . . . 19
2.4.1 The Maximum Size of 2-factor Isomorphic Graphs with
a 2-factor Consisting of k Cycles . . . . . . . . . . . . . . . . . . 19
2.4.2 The Maximum Size of 2-Factor Isomorphic Graphs with
Unspecified 2-factors . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.3 The Lower Bounds of the Maximum Size of 2-factor
Isomorphic Graphs with a 2-factor Consisting of
k Cycles or Unspecified 2-factor . . . . . . . . . . . . . . . . . . 23
3 General Graphs 26
3.1 Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.1 Small Order Hamiltonian Constructions . . . . . . . . . . . 27
3.1.2 Larger Order Hamiltonian Constructions . . . . . . . . . . 27
3.1.3 Construction Of Non-Hamiltonian 2-factor Isomorphic
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Bounding the Size of 2-factor Hamiltonian Graphs . . . . . 31
3.2.1 Bound for n <= 5 . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Bound for n = 6 . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.3 Bound for n >= 7 . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Bounding the size of Non-Hamiltonian 2-factor Isomorphic
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 Bound for Chords of Cycles in F and Edges on Cycles
in F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.2 Bound for Edges Between Cycles . . . . . . . . . . . . . . 34
3.3.3 Combining the Bounds and Rening . . . . . . . . . . . . . . 37
3.3.4 Finding and Attaining the Bound . . . . . . . . . . . . . . . 42
3.3.5 Computing the Bound . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Demonstrating that the Constructions are 2-factor
Isomorphic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.1 Showing that K_n is 2-factor Isomorphic for n <= 5 . . 49
3.4.2 Showing that G(6; V ) is 2-factor Isomorphic . . . . . . 49
3.4.3 Showing that G(n; V ) is 2-factor Isomorphic for
n >= 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.4 Demonstrating that the Construction for the
Non-Hamiltonian Case is 2-factor Isomorphic . . . . . . . . . . 50
3.5 Maximum Size of 2-factor Isomorphic Graphs with
Unspecified 2-factors . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.5.1 Maximum Size of 2-factor Isomorphic Graphs with an
Unspecified 2-factor . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5.2 Lower Bound of the Maximum Size of 2-factor Isomor-
phic Graphs with Unspecied 2-factor . . . . . . . . . . . . . . . 62
3.5.3 Maximum Size of 2-factor Isomorphic Graphs with a
2-factor consisting of k cycles . . . . . . . . . . . . . . . . . . . 68
3.5.4 Lower Bound of the Maximum Size of 2-factor Isomor-
phic Graphs with 2-factor consisting of k cycles . . . . . . . . 73
4 Other Directions 82
4.1 Vacuously 2-factor Isomorphic Graphs . . . . . . . . . . . . 83
4.1.1 Vacuously 2-factor Isomorphic Bipartite
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.1.2 Vacuously 2-factor Isomorphic General
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2 Other Possible Extensions . . . . . . . . . . . . . . . . . . . . 87
4.3 Related Questions . . . . . . . . . . . . . . . . . . . . . . . . . 89
Bibliography 93
About this Dissertation
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Palavra-chave | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
|
On the Number of Edges in 2-factor Isomorphic Graphs () | 2018-08-28 12:57:28 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|