Premium
Vertex pancyclic in‐tournaments
Author(s) -
Tewes Meike,
Volkmann Lutz
Publication year - 2001
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200102)36:2<84::aid-jgt4>3.0.co;2-d
Subject(s) - tournament , combinatorics , vertex (graph theory) , mathematics , conjecture , feedback vertex set , graph , upper and lower bounds , discrete mathematics , mathematical analysis
An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. The topic of this paper is to investigate vertex k ‐pancyclicity of in‐tournaments of order n , where for some 3 ≤ k ≤ n , every vertex belongs to a cycle of length p for every k ≤ p ≤ n . We give sharp lower bounds for the minimum degree such that a strong in‐tournament is vertex k ‐pancyclic for k ≤ 5 and k ≥ n − 3. In the latter case, we even show that the in‐tournaments in consideration are fully ( n − 3)‐extendable which means that every vertex belongs to a cycle of length n − 3 and that the vertex set of every cycle of length at least n − 3 is contained in a cycle of length one greater. In accordance with these results, we state the conjecture that every strong in‐tournament of order n with minimum degree greater than ${{9(n-k-1)}\over{5+6k+(-1)^k2^{-k+2}}}+1$ is vertex k ‐pancyclic for 5 < k < n − 3, and we present a family of examples showing that this bound would be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 84–104, 2001