An iterative approach to the traceability conjecture for oriented graphs (Q1953448)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An iterative approach to the traceability conjecture for oriented graphs |
scientific article |
Statements
An iterative approach to the traceability conjecture for oriented graphs (English)
0 references
7 June 2013
0 references
Summary: 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.
0 references
traceability conjecture
0 references
path partition conjecture
0 references
oriented graph
0 references
generalized tournament
0 references
traceable
0 references
\(k\)-traceable
0 references
longest path
0 references