A conjecture on cycle-pancyclism in tournaments

@article{HortensiaGaleana1998,
abstract = {Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote $I_γ (Cₖ) = |A(γ)∩A(Cₖ)|$, the number of arcs that γ and Cₖ have in common. Let $f(k,T,γ) = max\{I_γ(Cₖ)|Cₖ ⊂ T\}$ and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous papers we gave a characterization of f(n,k). In particular, the characterization implies that f(n,k) ≥ k-4. The purpose of this paper is to give some support to the following original conjecture: for any vertex v there exists a cycle of length k containing v with f(n,k) arcs in common with γ.},
author = {Hortensia Galeana-Sánchez, Sergio Rajsbaum},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Tournaments; pancyclism; cycle-pancyclism; tournament},
language = {eng},
number = {2},
pages = {243-251},
title = {A conjecture on cycle-pancyclism in tournaments},
url = {http://eudml.org/doc/270482},
volume = {18},
year = {1998},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - Sergio Rajsbaum
TI - A conjecture on cycle-pancyclism in tournaments
JO - Discussiones Mathematicae Graph Theory
PY - 1998
VL - 18
IS - 2
SP - 243
EP - 251
AB - Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote $I_γ (Cₖ) = |A(γ)∩A(Cₖ)|$, the number of arcs that γ and Cₖ have in common. Let $f(k,T,γ) = max{I_γ(Cₖ)|Cₖ ⊂ T}$ and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous papers we gave a characterization of f(n,k). In particular, the characterization implies that f(n,k) ≥ k-4. The purpose of this paper is to give some support to the following original conjecture: for any vertex v there exists a cycle of length k containing v with f(n,k) arcs in common with γ.
LA - eng
KW - Tournaments; pancyclism; cycle-pancyclism; tournament
UR - http://eudml.org/doc/270482
ER -