Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646678 | Discrete Mathematics | 2016 | 4 Pages |
Abstract
For k≥2k≥2, an oriented graph DD of order at least kk, is said to be kk-traceable if any subset of kk vertices of DD induces a traceable oriented graph. The traceability conjecture asserts that every kk-traceable oriented graph of order n≥2k−1n≥2k−1 is traceable. In this paper we prove that the traceability conjecture is true for triangle-free oriented graphs of order n=2k−1n=2k−1 or n≥3k−7n≥3k−7. In a second section, we prove that the traceability conjecture is true for oriented graphs of girth at least 5.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Nicolas Lichiardopol,