Download PDF - Infinite families of tight regular tournamentsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Infinite families of tight regular tournaments

Authors 1, 2

Affiliations

  1. Departamento de Matemáticas, Universidad Autónoma Metropolitana Iztapalapa, San Rafael Atlixco 186, Colonia Vicentina, 09340, México, D.F.
  2. Departamento de Matemáticas Aplicadas y Sistemas, Universidad Autónoma Metropolitana, Cuajimalpa, Prolongación Canal de Miramontes 3855, Colonia Ex-Hacienda San Juan de Dios, 14387, México, D.F.

Abstract

In this paper, we construct infinite families of tight regular tournaments. In particular, we prove that two classes of regular tournaments, tame molds and ample tournaments are tight. We exhibit an infinite family of 3-dichromatic tight tournaments. With this family we positively answer to one case of a conjecture posed by V. Neumann-Lara. Finally, we show that any tournament with a tight mold is also tight.

Keywords

ENG
regular tournament, acyclic disconnection, tight tournament, mold, tame mold, ample tournament, domination digraph

Bibliography

  1. J. Arocha, J. Bracho and V. Neumann-Lara, On the minimum size of tight hypergraphs, J. Graph Theory 16 (1992) 319-326, doi: 10.1002/jgt.3190160405.
  2. L.W. Beineke and K.B. Reid, Tournaments, in: L.W. Beineke, R.J. Wilson (Eds.), Selected Topics in Graph Theory (Academic Press, New York, 1979) 169-204.
  3. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Pub. Co., 1976).
  4. S. Bowser, C. Cable and R. Lundgren, Niche graphs and mixed pair graphs of tournaments, J. Graph Theory 31 (1999) 319-332, doi: 10.1002/(SICI)1097-0118(199908)31:4<319::AID-JGT7>3.0.CO;2-S
  5. H. Cho, F. Doherty, S-R. Kim and J. Lundgren, Domination graphs of regular tournaments II, Congr. Numer. 130 (1998) 95-111.
  6. H. Cho, S-R. Kim and J. Lundgren, Domination graphs of regular tournaments, Discrete Math. 252 (2002) 57-71, doi: 10.1016/S0012-365X(01)00289-8.
  7. D.C. Fisher, D. Guichard, J.R. Lundgren, S.K. Merz and K.B. Reid, Domination graphs with nontrivial components, Graphs Combin. 17 (2001) 227-236, doi: 10.1007/s003730170036.
  8. D.C. Fisher and J.R. Lundgren, Connected domination graphs of tournaments, J. Combin. Math. Combin. Comput. 31 (1999) 169-176.
  9. D.C. Fisher, J.R. Lundgren, S.K. Merz and K.B. Reid, The domination and competition graphs of a tournament, J. Graph Theory 29 (1998) 103-110, doi: 10.1002/(SICI)1097-0118(199810)29:2<103::AID-JGT6>3.0.CO;2-V
  10. H. Galeana-Sánchez and V. Neumann-Lara, A class of tight circulant tournaments, Discuss. Math. Graph Theory 20 (2000) 109-128, doi: 10.7151/dmgt.1111.
  11. B. Llano and V. Neumann-Lara, Circulant tournaments of prime order are tight, (submitted).
  12. J.W. Moon, Topics on Tournaments (Holt, Rinehart & Winston, New York, 1968).
  13. V. Neumann-Lara, The dichromatic number of a digraph, J. Combin. Theory (B) 33 (1982) 265-270, doi: 10.1016/0095-8956(82)90046-6.
  14. V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197/198 (1999) 617-632.
  15. V. Neumann-Lara and M. Olsen, Tame tournaments and their dichromatic number, (submitted).
  16. K.B. Reid, Tournaments, in: Jonathan Gross, Jay Yellen (eds.), Handbook of Graph Theory (CRC Press, 2004) 156-184.
Discussiones Mathematicae Graph Theory
2007/27/2
Export to PBN, Opens in new tab
Pages:
299-311
Main language of publication
English
Received
2006-04-24
Accepted
2006-11-14
Published
2007

DOI: 10.7151/dmgt.1362

Exact and natural sciences