Article ID Journal Published Year Pages File Type
4646678 Discrete Mathematics 2016 4 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,