Geodesic
Hamiltonicity of \(k\)-traceable graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 \geq 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 \le 10$, we determine the exact value of $H(k)$. For $k \ge 11$, we show that $k+2 \le H(k) \le \frac{1}{2}(3k-5)$.
DOI : 10.37236/550
Classification : 05C45, 05C38
Mots-clés : Hamiltonian graph, traceable, toughness 
@article{10_37236_550,
     author = {Frank Bullock and Peter Dankelmann and Marietjie Frick and Michael A. Henning and Ortrud R. Oellermann and Susan van Aardt},
     title = {Hamiltonicity of \(k\)-traceable graphs},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/550},
     zbl = {1217.05129},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/550/}
}
TY  - JOUR
AU  - Frank Bullock
AU  - Peter Dankelmann
AU  - Marietjie Frick
AU  - Michael A. Henning
AU  - Ortrud R. Oellermann
AU  - Susan van Aardt
TI  - Hamiltonicity of \(k\)-traceable graphs
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/550/
DO  - 10.37236/550
ID  - 10_37236_550
ER  - 
%0 Journal Article
%A Frank Bullock
%A Peter Dankelmann
%A Marietjie Frick
%A Michael A. Henning
%A Ortrud R. Oellermann
%A Susan van Aardt
%T Hamiltonicity of \(k\)-traceable graphs
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/550/
%R 10.37236/550
%F 10_37236_550
Frank Bullock; Peter Dankelmann; Marietjie Frick; Michael A. Henning; Ortrud R. Oellermann; Susan van Aardt. Hamiltonicity of \(k\)-traceable graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/550

Cité par Sources :