A conjecture on cycle-pancyclism in tournaments
Hortensia Galeana‐Sánchez, Sergio Rajsbaum · Discussiones Mathematicae Graph Theory · 1998
LetT be a Hamiltonian tournament withn 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 Ck of length k in T we denoteI (Ck) =jA( )\A(Ck)j, the number of arcs that and Ck have in common. Let f(k;T; ) = maxfI (Ck)jCk Tg and f(n;k) = minff(k;T; )jT is a Hamiltonian tournament with n vertices, and a Hamiltonian cycle of Tg. 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 conjecture that for any vertex v there exists a cycle of length k containing v with f(n;k) arcs in common with . We present various particular cases in which this equality holds.