DMGT

Discussiones Mathematicae Graph Theory 27(2) (2007) 299-311
DOI: https://doi.org/10.7151/dmgt.1362

INFINITE FAMILIES OF TIGHT REGULAR TOURNAMENTS

Bernardo Llano

Departamento de Matemáticas
Universidad Autónoma Metropolitana Iztapalapa
San Rafael Atlixco 186, Colonia Vicentina, 09340, México, D.F.
e-mail: llano@xanum.uam.mx

Mika Olsen

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.
e-mail: olsen@math.unam.mx

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: regular tournament, acyclic disconnection, tight tournament, mold, tame mold, ample tournament, domination digraph.

2000 Mathematics Subject Classification: Primary: 05C20, 05C15.

References

[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.

Received 24 April 2006
Revised 14 November 2006
Accepted 14 November 2006