A linear bound towards the traceability conjecture

MaRDI QIDQ895060zbMATH OpenFDO

Authors Susan Van Aardt, Marietjie Frick, Nicolas Lichiardopol, Jean E. Dunbar

Publication date 26 November 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p26

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(k\)-traceablegeneralized tournamentoriented graphpath partition conjecturetraceability conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Review text

Summary: A digraph is \(k\)-traceable if its order is at least \(k\) and each of its subdigraphs of order \(k\) is traceable. An oriented graph is a digraph without 2-cycles. The 2-traceable oriented graphs are exactly the nontrivial tournaments, so \(k\)-traceable oriented graphs may be regarded as generalized tournaments. It is well-known that all tournaments are traceable. We denote by \(t(k)\) the smallest integer bigger than or equal to \(k\) such that every \(k\)-traceable oriented graph of order at least \(t(k)\) is traceable. The traceability conjecture states that \(t(k) \leq 2k-1\) for every \(k\geq 2\) [the third author et al., ibid. 15, No. 1, Research Paper R150, 13 p. (2008; Zbl 1178.05046)]. We show that for \(k \geq 2\), every \(k\)-traceable oriented graph with independence number 2 and order at least 4\(k\)-12 is traceable. This is the last open case in giving an upper bound for \(t(k)\) that is linear in \(k\).

Recommendations

• Progress on the traceability conjecture for oriented graphs
• Traceability of k-traceable oriented graphs
• Triangle-free oriented graphs and the traceability conjecture
• A traceability conjecture for oriented graphs
• Computational results on the traceability of oriented graphs of small order

Cites work

• A traceability conjecture for oriented graphs
• An iterative approach to the traceability conjecture for oriented graphs
• Computational results on the traceability of oriented graphs of small order
• Cycles in \(k\)-traceable oriented graphs
• Digraphs
• Every finite strongly connected digraph of stability 2 has a Hamiltonian path
• scientific article; zbMATH DE number 3838057 (Why is no real title available?)
• Infinite families of 2-hypohamiltonian/2-hypotraceable oriented graphs
• Longest path partitions in generalizations of tournaments
• Progress on the traceability conjecture for oriented graphs
• Stable set meeting every longest path
• The directed path partition conjecture
• The order of hypotraceable oriented graphs
• Traceability of k-traceable oriented graphs

Cited in

(11)

• A traceability conjecture for oriented graphs
• Lower bounds for trace reconstruction
• The order of hypotraceable oriented graphs
• Every 8-traceable oriented graph is traceable
• Characterizations of k-traceable graphs and oriented graphs
• Progress on the traceability conjecture for oriented graphs
• Computational results on the traceability of oriented graphs of small order
• Forbidden subdigraphs conditions on the traceability conjecture
• On k-anti-traceability of oriented graphs
• Triangle-free oriented graphs and the traceability conjecture
• Traceability of k-traceable oriented graphs

This page was built for publication: A linear bound towards the traceability conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q895060)