Geodesic
An iterative approach to the traceability conjecture for oriented graphs
Susan van Aardt1 ; Alewyn Burger2 ; Jean Dunbar3 ; Marietjie Frick1 ; John Harris4 ; Joy Singleton1
1University of South Africa
2University of Stellenbosch
3Converse College
4Furman University
The electronic journal of combinatorics, Tome 20 (2013) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A digraph is $k$-traceable if its order is at least $k$ and each of its subdigraphs of order $k$ is traceable. The Traceability Conjecture (TC) states that for $k\geq 2$ every $k$-traceable oriented graph of order at least $2k-1$ is traceable. It has been shown that for $2\leq k\leq 6$, every $k$-traceable oriented graph is traceable. We develop an iterative procedure to extend previous results regarding the TC. In particular, we prove that every $7$-traceable oriented graph of order at least 9 is traceable and every 8-traceable graph of order at least 14 is traceable.
DOI : 10.37236/2498
Classification : 05C20, 05C38
Mots-clés : traceability conjecture, path partition conjecture, oriented graph, generalized tournament, traceable, \(k\)-traceable, longest path

Susan van Aardt  1   ; Alewyn Burger  2   ; Jean Dunbar  3   ; Marietjie Frick  1   ; John Harris  4   ; Joy Singleton  1

1 University of South Africa
2 University of Stellenbosch
3 Converse College
4 Furman University 
@article{10_37236_2498,
     author = {Susan van Aardt and Alewyn Burger and Jean Dunbar and Marietjie Frick and John Harris and Joy Singleton},
     title = {An iterative approach to the traceability conjecture for oriented graphs},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {1},
     doi = {10.37236/2498},
     zbl = {1266.05044},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2498/}
}
TY  - JOUR
AU  - Susan van Aardt
AU  - Alewyn Burger
AU  - Jean Dunbar
AU  - Marietjie Frick
AU  - John Harris
AU  - Joy Singleton
TI  - An iterative approach to the traceability conjecture for oriented graphs
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2498/
DO  - 10.37236/2498
ID  - 10_37236_2498
ER  - 
%0 Journal Article
%A Susan van Aardt
%A Alewyn Burger
%A Jean Dunbar
%A Marietjie Frick
%A John Harris
%A Joy Singleton
%T An iterative approach to the traceability conjecture for oriented graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2498/
%R 10.37236/2498
%F 10_37236_2498
Susan van Aardt; Alewyn Burger; Jean Dunbar; Marietjie Frick; John Harris; Joy Singleton. An iterative approach to the traceability conjecture for oriented graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2498

Cité par Sources :