A conjecture on cycle-pancyclism in tournaments
Hortensia Galeana-Sánchez ; Sergio Rajsbaum
Discussiones Mathematicae Graph Theory, Tome 18 (1998), p. 243-251 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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,γ)=maxIγ(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 γ.

Publié le : 1998-01-01
EUDML-ID : urn:eudml:doc:270482 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1080,
     author = {Hortensia Galeana-S\'anchez and Sergio Rajsbaum},
     title = {A conjecture on cycle-pancyclism in tournaments},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {18},
     year = {1998},
     pages = {243-251},
     zbl = {0928.05031},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1080}
}

Hortensia Galeana-Sánchez; Sergio Rajsbaum. A conjecture on cycle-pancyclism in tournaments. Discussiones Mathematicae Graph Theory, Tome 18 (1998) pp. 243-251. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1080/

[000] [1] B. Alspach, Cycles of each length in regular tournaments, Canadian Math. Bull. 10 (1967) 283-286, doi: 10.4153/CMB-1967-028-6. | Zbl 0148.43602

[001] [2] J. Bang-Jensen and G. Gutin, Paths, Trees and Cycles in Tournaments, Congressus Numer. 115 (1996) 131-170.

[002] [3] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs & Digraphs (Prindle, Weber & Schmidt International Series, 1979). | Zbl 0403.05027

[003] [4] J.C. Bermond and C. Thomasen, Cycles in digraphs: A survey, J. Graph Theory 5 (1981) 1-43, doi: 10.1002/jgt.3190050102. | Zbl 0458.05035

[004] [5] H. Galeana-Sánchez and S. Rajsbaum, Cycle-Pancyclism in Tournaments I, Graphs and Combinatorics 11 (1995) 233-243, doi: 10.1007/BF01793009. | Zbl 0833.05039

[005] [6] H. Galeana-Sánchez and S. Rajsbaum, Cycle-Pancyclism in Tournaments II, Graphs and Combinatorics 12 (1996) 9-16, doi: 10.1007/BF01858440. | Zbl 0844.05047

[006] [7] H. Galeana-Sánchez and S. Rajsbaum, Cycle-Pancyclism in Tournaments III, Graphs and Combinatorics 13 (1997) 57-63, doi: 10.1007/BF01202236. | Zbl 0868.05028

[007] [8] J.W. Moon, On Subtournaments of a Tournament, Canad. Math. Bull. 9 (1966) 297-301, doi: 10.4153/CMB-1966-038-7. | Zbl 0141.41204

[008] [9] J.W. Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968). | Zbl 0191.22701

[009] [10] J.W. Moon, On k-cyclic and Pancyclic Arcs in Strong Tournaments, J. Combinatorics, Information and System Sci. 19 (1994) 207-214. | Zbl 0860.05039

[010] [11] D.F. Robinson and L.R. Foulds, Digraphs: Theory and Techniques (Gordon and Breach Science Publishing, 1980). | Zbl 0484.05034

[011] [12] Z.-S. Wu, k.-M. Zhang and Y. Zou, A Necessary and Sufficient Condition for Arc-pancyclicity of Tournaments, Sci. Sinica 8 (1981) 915-919.