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...

Full description

Saved in:
Bibliographic Details
Main Author: Gao, Mou
Other Authors: Dmitrii V Pasechnik
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