Infinite families of tight regular tournaments
Bernardo Llano ; Mika Olsen
Discussiones Mathematicae Graph Theory, Tome 27 (2007), p. 299-311 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2007-01-01
EUDML-ID : urn:eudml:doc:270731 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1362,
     author = {Bernardo Llano and Mika Olsen},
     title = {Infinite families of tight regular tournaments},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {27},
     year = {2007},
     pages = {299-311},
     zbl = {1133.05042},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1362}
}

Bernardo Llano; Mika Olsen. Infinite families of tight regular tournaments. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 299-311. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1362/

[000] [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. | Zbl 0776.05079

[001] [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. | Zbl 0434.05037

[002] [3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Pub. Co., 1976). | Zbl 1226.05083

[003] [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 | Zbl 0942.05027

[004] [5] H. Cho, F. Doherty, S-R. Kim and J. Lundgren, Domination graphs of regular tournaments II, Congr. Numer. 130 (1998) 95-111. | Zbl 0952.05052

[005] [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. | Zbl 0993.05106

[006] [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. | Zbl 0989.05081

[007] [8] D.C. Fisher and J.R. Lundgren, Connected domination graphs of tournaments, J. Combin. Math. Combin. Comput. 31 (1999) 169-176. | Zbl 0942.05028

[008] [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 | Zbl 0919.05024

[009] [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. | Zbl 0969.05031

[010] [11] B. Llano and V. Neumann-Lara, Circulant tournaments of prime order are tight, (submitted). | Zbl 1198.05083

[011] [12] J.W. Moon, Topics on Tournaments (Holt, Rinehart & Winston, New York, 1968). | Zbl 0191.22701

[012] [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. | Zbl 0506.05031

[013] [14] V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197/198 (1999) 617-632. | Zbl 0928.05033

[014] [15] V. Neumann-Lara and M. Olsen, Tame tournaments and their dichromatic number, (submitted). | Zbl 1207.05072

[015] [16] K.B. Reid, Tournaments, in: Jonathan Gross, Jay Yellen (eds.), Handbook of Graph Theory (CRC Press, 2004) 156-184.