On the Number of Edges in 2-factor Isomorphic Graphs Público

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

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
Palavra-chave	hamiltonian 2-factor 2-factor isomorphic constructive bound graph theory extremal maximum size combinatorics
Committee Chair / Thesis Advisor	Gould, Ronald J, Emory University
Committee Members	Duffus, Dwight A, Emory University Grigni, Michelangelo, Emory University

Última modificação

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	On the Number of Edges in 2-factor Isomorphic Graphs ()	2018-08-28 12:57:28 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions