Hamiltonicity of k-traceable graphs

Frank Bullock; Peter Dankelmann; Marietjie Frick; Michael A. Henning; Ortrud R. Oellermann; Susan van Aardt

doi:10.37236/550

Hamiltonicity of k-traceable graphs

Frank Bullock, Peter Dankelmann, Marietjie Frick, Michael A. Henning, Ortrud R. Oellermann, Susan van Aardt

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let G be a graph. A Hamilton path in G is a path containing every vertex of G. The graph G is traceable if it contains a Hamilton path, while G is k-traceable if every induced subgraph of G of order k is traceable. In this paper, we study hamiltonicity of k-traceable graphs. For k ≥ 2 an integer, we define H(k) to be the largest integer such that there exists a k-traceable graph of order H(k) that is nonhamiltonian. For k ≤ 10, we determine the exact value of H(k). For k ≥ 11, we show that k + 2 ≤ H(k) ≤ 1/2 (3k - 5).

Original language	English
Journal	Electronic Journal of Combinatorics
Volume	18
Issue number	1
DOIs	https://doi.org/10.37236/550
Publication status	Published - 2011

Keywords

Hamiltonian graph
Toughness
Traceable

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/550

Cite this

@article{99fd6d74e0734f039909a9d789d55b49,

title = "Hamiltonicity of k-traceable graphs",

abstract = "Let G be a graph. A Hamilton path in G is a path containing every vertex of G. The graph G is traceable if it contains a Hamilton path, while G is k-traceable if every induced subgraph of G of order k is traceable. In this paper, we study hamiltonicity of k-traceable graphs. For k ≥ 2 an integer, we define H(k) to be the largest integer such that there exists a k-traceable graph of order H(k) that is nonhamiltonian. For k ≤ 10, we determine the exact value of H(k). For k ≥ 11, we show that k + 2 ≤ H(k) ≤ 1/2 (3k - 5).",

keywords = "Hamiltonian graph, Toughness, Traceable",

author = "Frank Bullock and Peter Dankelmann and Marietjie Frick and Henning, {Michael A.} and Oellermann, {Ortrud R.} and {van Aardt}, Susan",

year = "2011",

doi = "10.37236/550",

language = "English",

volume = "18",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - Hamiltonicity of k-traceable graphs

AU - Bullock, Frank

AU - Dankelmann, Peter

AU - Frick, Marietjie

AU - Henning, Michael A.

AU - Oellermann, Ortrud R.

AU - van Aardt, Susan

PY - 2011

Y1 - 2011

N2 - Let G be a graph. A Hamilton path in G is a path containing every vertex of G. The graph G is traceable if it contains a Hamilton path, while G is k-traceable if every induced subgraph of G of order k is traceable. In this paper, we study hamiltonicity of k-traceable graphs. For k ≥ 2 an integer, we define H(k) to be the largest integer such that there exists a k-traceable graph of order H(k) that is nonhamiltonian. For k ≤ 10, we determine the exact value of H(k). For k ≥ 11, we show that k + 2 ≤ H(k) ≤ 1/2 (3k - 5).

AB - Let G be a graph. A Hamilton path in G is a path containing every vertex of G. The graph G is traceable if it contains a Hamilton path, while G is k-traceable if every induced subgraph of G of order k is traceable. In this paper, we study hamiltonicity of k-traceable graphs. For k ≥ 2 an integer, we define H(k) to be the largest integer such that there exists a k-traceable graph of order H(k) that is nonhamiltonian. For k ≤ 10, we determine the exact value of H(k). For k ≥ 11, we show that k + 2 ≤ H(k) ≤ 1/2 (3k - 5).

KW - Hamiltonian graph

KW - Toughness

KW - Traceable

UR - http://www.scopus.com/inward/record.url?scp=79955717274&partnerID=8YFLogxK

U2 - 10.37236/550

DO - 10.37236/550

M3 - Article

AN - SCOPUS:79955717274

SN - 1077-8926

VL - 18

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

ER -

Hamiltonicity of k-traceable graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this