Infinite families of tight regular tournaments

• Autorzy: Bernardo Llano , Mika Olsen
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

regular tournament; acyclic disconnection; tight tournament; mold; tame mold; ample tournament; domination digraph

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C20: Directed graphs (digraphs), tournaments

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2007
• Tom: 27
• Numer: 2
• Strony: 299-311

Daty

wydano

2007

otrzymano

2006-04-24

poprawiono

2006-11-14

zaakceptowano

2006-11-14

Twórcy

autor

Bernardo Llano

• Departamento de Matemáticas, Universidad Autónoma Metropolitana Iztapalapa, San Rafael Atlixco 186, Colonia Vicentina, 09340, México, D.F.

autor

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.

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1362