Infinite families of tight regular tournaments

Bernardo Llano; Mika Olsen

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 2, page 299-311
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Bernardo Llano, and Mika Olsen. "Infinite families of tight regular tournaments." Discussiones Mathematicae Graph Theory 27.2 (2007): 299-311. <http://eudml.org/doc/270731>.

@article{BernardoLlano2007,
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.},
author = {Bernardo Llano, Mika Olsen},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {regular tournament; acyclic disconnection; tight tournament; mold; tame mold; ample tournament; domination digraph},
language = {eng},
number = {2},
pages = {299-311},
title = {Infinite families of tight regular tournaments},
url = {http://eudml.org/doc/270731},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Bernardo Llano
AU - Mika Olsen
TI - Infinite families of tight regular tournaments
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 2
SP - 299
EP - 311
AB - 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.
LA - eng
KW - regular tournament; acyclic disconnection; tight tournament; mold; tame mold; ample tournament; domination digraph
UR - http://eudml.org/doc/270731
ER -

References

top
  1. [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. Zbl0776.05079
  2. [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. Zbl0434.05037
  3. [3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Pub. Co., 1976). Zbl1226.05083
  4. [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 Zbl0942.05027
  5. [5] H. Cho, F. Doherty, S-R. Kim and J. Lundgren, Domination graphs of regular tournaments II, Congr. Numer. 130 (1998) 95-111. Zbl0952.05052
  6. [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. Zbl0993.05106
  7. [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. Zbl0989.05081
  8. [8] D.C. Fisher and J.R. Lundgren, Connected domination graphs of tournaments, J. Combin. Math. Combin. Comput. 31 (1999) 169-176. Zbl0942.05028
  9. [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 Zbl0919.05024
  10. [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. Zbl0969.05031
  11. [11] B. Llano and V. Neumann-Lara, Circulant tournaments of prime order are tight, (submitted). Zbl1198.05083
  12. [12] J.W. Moon, Topics on Tournaments (Holt, Rinehart & Winston, New York, 1968). Zbl0191.22701
  13. [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. Zbl0506.05031
  14. [14] V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197/198 (1999) 617-632. Zbl0928.05033
  15. [15] V. Neumann-Lara and M. Olsen, Tame tournaments and their dichromatic number, (submitted). Zbl1207.05072
  16. [16] K.B. Reid, Tournaments, in: Jonathan Gross, Jay Yellen (eds.), Handbook of Graph Theory (CRC Press, 2004) 156-184. 

NotesEmbed ?

top

You must be logged in to post comments.