Solution of a conjecture of Tewes and Volkmann regarding extendable cycles in in‐tournaments
Dirk Meierling · Journal of Graph Theory · 2009
Abstract A directed cycle C of a digraph D is extendable if there exists a directed cycle C ′ in D that contains all vertices of C and an additional one. In 1989, Hendry defined a digraph D to be cycle extendable if it contains a directed cycle and every non‐Hamiltonian directed cycle of D is extendable. Furthermore, D is fully cycle extendable if it is cycle extendable and every vertex of D belongs to a directed cycle of length three. In 2001, Tewes and Volkmann extended these definitions in considering only directed cycles whose length exceed a certain bound 3≤ k }{{8n-17}\over {31}}$ , then D is fully ( $n-\lfloor {{4\delta+1} \over {3}}\rfloor$ ) ‐extendable. In this article we shall see that if $3 \leq \delta \leq {{8n-17} \over {31}}$ , every vertex of D belongs to a directed cycle of length $n-\lfloor {{4\delta+1} \over {3}}\rfloor$ , which means that D is fully ( $n-\lfloor {{4\delta+1} \over {3}}\rfloor$ ) ‐extendable. This confirms a conjecture of Tewes and Volkmann. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 82–92, 2010