The k-walks in 2K2-free graphs
After a review of Hamiltonicity of graphs and related concepts, we discuss several generalizations of Hamilton cycles: k-walks, k-trees, Hamilton-prisms and edge-dominating cycles, and investigate the relationship between them. In particular, we focus on the Jackson-Wormald conjecture and show that...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
Format: | Theses and Dissertations |
Language: | English |
Published: |
2016
|
Subjects: | |
Online Access: | http://hdl.handle.net/10356/66352 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-66352 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-663522023-02-28T23:57:27Z The k-walks in 2K2-free graphs Gao, Mou Dmitrii V Pasechnik School of Physical and Mathematical Sciences DRNTU::Science After a review of Hamiltonicity of graphs and related concepts, we discuss several generalizations of Hamilton cycles: k-walks, k-trees, Hamilton-prisms and edge-dominating cycles, and investigate the relationship between them. In particular, we focus on the Jackson-Wormald conjecture and show that it holds for a graph with an edge-dominating cycle. The latter gives us our central result: an efficient algorithmic proof of Jackson-Wormald conjecture for 2K_2-free graphs. Another main result is that each (1+\epsilon) -tough 2K_2-free graph is prism-Hamiltonian. Generally, being prism-Hamiltonian is a stronger property than admitting k-walks for all k\ge2, but weaker than being traceable. Finally, we present several results on the existence of 2-walks under the 1-toughness assumption for some other graphs, and pose conjectures for further research. Doctor of Philosophy (SPMS) 2016-03-30T02:59:52Z 2016-03-30T02:59:52Z 2016 Thesis http://hdl.handle.net/10356/66352 en 109 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
DRNTU::Science |
spellingShingle |
DRNTU::Science Gao, Mou The k-walks in 2K2-free graphs |
description |
After a review of Hamiltonicity of graphs and related concepts, we discuss several generalizations of Hamilton cycles: k-walks, k-trees, Hamilton-prisms and edge-dominating cycles, and investigate the relationship between them. In particular, we focus on the Jackson-Wormald conjecture and show that it holds for a graph with an edge-dominating cycle. The latter gives us our central result: an efficient algorithmic proof of Jackson-Wormald conjecture for 2K_2-free graphs. Another main result is that each (1+\epsilon) -tough 2K_2-free graph is prism-Hamiltonian. Generally, being prism-Hamiltonian is a stronger property than admitting k-walks for all k\ge2, but weaker than being traceable. Finally, we present several results on the existence of 2-walks under the 1-toughness assumption for some other graphs, and pose conjectures for further research. |
author2 |
Dmitrii V Pasechnik |
author_facet |
Dmitrii V Pasechnik Gao, Mou |
format |
Theses and Dissertations |
author |
Gao, Mou |
author_sort |
Gao, Mou |
title |
The k-walks in 2K2-free graphs |
title_short |
The k-walks in 2K2-free graphs |
title_full |
The k-walks in 2K2-free graphs |
title_fullStr |
The k-walks in 2K2-free graphs |
title_full_unstemmed |
The k-walks in 2K2-free graphs |
title_sort |
k-walks in 2k2-free graphs |
publishDate |
2016 |
url |
http://hdl.handle.net/10356/66352 |
_version_ |
1759857758116511744 |