A conjecture on cycle-pancyclism in tournaments

Hortensia Galeana-Sánchez; Sergio Rajsbaum

Discussiones Mathematicae Graph Theory (1998)

  • Volume: 18, Issue: 2, page 243-251
  • ISSN: 2083-5892

Abstract

top
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 , γ ) = m a x 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 γ.

How to cite

top

Hortensia Galeana-Sánchez, and Sergio Rajsbaum. "A conjecture on cycle-pancyclism in tournaments." Discussiones Mathematicae Graph Theory 18.2 (1998): 243-251. <http://eudml.org/doc/270482>.

@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 -

References

top
  1. [1] B. Alspach, Cycles of each length in regular tournaments, Canadian Math. Bull. 10 (1967) 283-286, doi: 10.4153/CMB-1967-028-6. Zbl0148.43602
  2. [2] J. Bang-Jensen and G. Gutin, Paths, Trees and Cycles in Tournaments, Congressus Numer. 115 (1996) 131-170. 
  3. [3] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs & Digraphs (Prindle, Weber & Schmidt International Series, 1979). Zbl0403.05027
  4. [4] J.C. Bermond and C. Thomasen, Cycles in digraphs: A survey, J. Graph Theory 5 (1981) 1-43, doi: 10.1002/jgt.3190050102. Zbl0458.05035
  5. [5] H. Galeana-Sánchez and S. Rajsbaum, Cycle-Pancyclism in Tournaments I, Graphs and Combinatorics 11 (1995) 233-243, doi: 10.1007/BF01793009. Zbl0833.05039
  6. [6] H. Galeana-Sánchez and S. Rajsbaum, Cycle-Pancyclism in Tournaments II, Graphs and Combinatorics 12 (1996) 9-16, doi: 10.1007/BF01858440. Zbl0844.05047
  7. [7] H. Galeana-Sánchez and S. Rajsbaum, Cycle-Pancyclism in Tournaments III, Graphs and Combinatorics 13 (1997) 57-63, doi: 10.1007/BF01202236. Zbl0868.05028
  8. [8] J.W. Moon, On Subtournaments of a Tournament, Canad. Math. Bull. 9 (1966) 297-301, doi: 10.4153/CMB-1966-038-7. Zbl0141.41204
  9. [9] J.W. Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968). Zbl0191.22701
  10. [10] J.W. Moon, On k-cyclic and Pancyclic Arcs in Strong Tournaments, J. Combinatorics, Information and System Sci. 19 (1994) 207-214. Zbl0860.05039
  11. [11] D.F. Robinson and L.R. Foulds, Digraphs: Theory and Techniques (Gordon and Breach Science Publishing, 1980). Zbl0484.05034
  12. [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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.