Cycles in \(k\)-traceable oriented graphs (Q641171)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cycles in \(k\)-traceable oriented graphs |
scientific article |
Statements
Cycles in \(k\)-traceable oriented graphs (English)
0 references
21 October 2011
0 references
A digraph of order at least \(k\) is said to be \(k\)-traceable if each of its sub-digraphs of order \(k\) is traceable. The paper presents some results pertaining to various cycle properties of strong \(k\)-traceable oriented graphs and investigates the extent to which pancyclicity is retained by strong \(k\)-traceable oriented graphs. In addition, it establishes an upper bound on the order of \(k\)-traceable oriented graphs having a strong component with girth greater than 3. It is also shown that the Path Partition Conjecture holds for 1-deficient oriented graphs having a strong component with girth at least 6.
0 references
oriented graph
0 references
tournament
0 references
pancyclic digraph
0 references
\(k\)-traceable
0 references
traceability conjecture
0 references
path partition conjecture
0 references