Premium
Edge‐disjoint Hamiltonian cycles in hypertournaments
Author(s) -
Petrovic Vojislav,
Thomassen Carsten
Publication year - 2006
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/jgt.20120
Subject(s) - tournament , combinatorics , mathematics , disjoint sets , hamiltonian path , hamiltonian (control theory) , graph , enhanced data rates for gsm evolution , complete graph , discrete mathematics , computer science , mathematical optimization , telecommunications
We introduce a method for reducing k ‐tournament problems, for k ≥ 3, to ordinary tournaments, that is, 2‐tournaments. It is applied to show that a k ‐tournament on n ≥ k + 1 + 24 d vertices (when k ≥ 4) or on n ≥ 30 d + 2 vertices (when k = 3) has d edge‐disjoint Hamiltonian cycles if and only if it is d ‐edge‐connected. Ironically, this is proved by ordinary tournament arguments although it only holds for k ≥ 3. We also characterizatize the pancyclic k ‐tournaments, a problem posed by Gutin and Yeo.(Our characterization is slightly incomplete in that we prove it only for n large compared to k .). © 2005 Wiley Periodicals, Inc. J Graph Theory