Geodesic
A traceability conjecture for oriented graphs
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A (di)graph $G$ of order $n$ is $k$-traceable (for some $k$, $1\leq k\leq n$) if every induced sub(di)graph of $G$ of order $k$ is traceable. It follows from Dirac's degree condition for hamiltonicity that for $k\geq2$ every $k$-traceable graph of order at least $2k-1$ is hamiltonian. The same is true for strong oriented graphs when $k=2,3,4,$ but not when $k\geq5$. However, we conjecture that for $k\geq2$ every $k$-traceable oriented graph of order at least $2k-1$ is traceable. The truth of this conjecture would imply the truth of an important special case of the Path Partition Conjecture for Oriented Graphs. In this paper we show the conjecture is true for $k \leq 5$ and for certain classes of graphs. In addition we show that every strong $k$-traceable oriented graph of order at least $6k-20$ is traceable. We also characterize those graphs for which all walkable orientations are $k$-traceable.
DOI : 10.37236/874
Classification : 05C20, 05C38, 05C15, 05C45
Mots-clés : traceable graph, traceable digraph, traceability, hamiltonicity, hamiltonian graph, strong oriented graphs, path partition conjecture for oriented graphs 
@article{10_37236_874,
     author = {Marietjie Frick and Susan A van Aardt and Jean E Dunbar and Morten H Nielsen and Ortrud R Oellermann},
     title = {A traceability conjecture for oriented graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/874},
     zbl = {1178.05046},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/874/}
}
TY  - JOUR
AU  - Marietjie Frick
AU  - Susan A van Aardt
AU  - Jean E Dunbar
AU  - Morten H Nielsen
AU  - Ortrud R Oellermann
TI  - A traceability conjecture for oriented graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/874/
DO  - 10.37236/874
ID  - 10_37236_874
ER  - 
%0 Journal Article
%A Marietjie Frick
%A Susan A van Aardt
%A Jean E Dunbar
%A Morten H Nielsen
%A Ortrud R Oellermann
%T A traceability conjecture for oriented graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/874/
%R 10.37236/874
%F 10_37236_874
Marietjie Frick; Susan A van Aardt; Jean E Dunbar; Morten H Nielsen; Ortrud R Oellermann. A traceability conjecture for oriented graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/874

Cité par Sources :