1. bookVolume 38 (2018): Issue 3 (August 2018)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The {−2,−1}-Selfdual and Decomposable Tournaments

Published Online: 19 Jun 2018
Volume & Issue: Volume 38 (2018) - Issue 3 (August 2018)
Page range: 743 - 789
Received: 03 Aug 2016
Accepted: 06 Feb 2017
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

We only consider finite tournaments. The dual of a tournament is obtained by reversing all the arcs. A tournament is selfdual if it is isomorphic to its dual. Given a tournament T, a subset X of V (T) is a module of T if each vertex outside X dominates all the elements of X or is dominated by all the elements of X. A tournament T is decomposable if it admits a module X such that 1 < |X| < |V (T)|.

We characterize the decomposable tournaments whose subtournaments obtained by removing one or two vertices are selfdual. We deduce the following result. Let T be a non decomposable tournament. If the subtournaments of T obtained by removing two or three vertices are selfdual, then the subtournaments of T obtained by removing a single vertex are not decomposable. Lastly, we provide two applications to tournaments reconstruction.

Keywords

MSC 2010

[1] M. Achour, Y. Boudabbous and A. Boussaïri, The {−3}-reconstruction and the {−3}-self duality of tournaments, Ars Combin. 122 (2015) 355–377.Search in Google Scholar

[2] M. Basso-Gerbelli and P. Ille, La reconstruction des relations définies par interdits, C. R. Acad. Sci. Paris, Sér. I Math. 316 (1993) 1229–1234.Search in Google Scholar

[3] H. Belkhechine, I. Boudabbous and J. Dammak, Morphologie des tournois (−1)-critiques, C. R. Acad. Sci. Paris, Sér. I Math. 345 (2007) 663–666. doi:10.1016/j.crma.2007.11.00610.1016/j.crma.2007.11.006Search in Google Scholar

[4] A. Bondy and R.L. Hemminger, Graph reconstruction, a survey, J. Graph Theory 1 (1977) 227–268. doi:10.1002/jgt.319001030610.1002/jgt.3190010306Search in Google Scholar

[5] H. Bouchaala, Sur la répartition des diamants dans un tournoi, C. R. Acad. Sci. Paris, Sér. I Math. 338 (2004) 109–112. doi:10.1016/j.crma.2003.11.01810.1016/j.crma.2003.11.018Search in Google Scholar

[6] H. Bouchaala and Y. Boudabbous, La {−k}-autodualité des sommes lexicographiques finies de tournois suivant un 3-cycle ou un tournoi critique, Ars Combin. 81 (2006) 33–64.Search in Google Scholar

[7] Y. Boudabbous, J. Dammak and P. Ille, Indecomposability and duality of tournaments, Discrete Math. 223 (2000) 55–82. doi:10.1016/S0012-365X(00)00040-610.1016/S0012-365X(00)00040-6Search in Google Scholar

[8] Y. Boudabbous and A. Boussaïri, Reconstruction des tournois et dualité, C. R. Acad. Sci. Paris, Sér. I Math. 320 (1995) 397–400.Search in Google Scholar

[9] Y. Boudabbous and P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, Discrete Math. 309 (2009) 2839–2846. doi:10.1016/j.disc.2008.07.01510.1016/j.disc.2008.07.015Search in Google Scholar

[10] Y. Boudabbous and P. Ille, Cut-primitive directed graphs versus clan-primitive directed graphs, Adv. Pure Appl. Math. 1 (2010) 223–231. doi:10.1515/apam.2010.01310.1515/apam.2010.013Search in Google Scholar

[11] A. Boussaïri, Décomposabilité, dualité et groupes finis en théorie des relations (Ph.D. Thesis, Université Claude Bernard, Lyon I, 1995).Search in Google Scholar

[12] A. Boussaïri, P. Ille, G. Lopez and S. Thomassé, The C3-structure of the tournaments, Discrete Math. 277 (2004) 29–43. doi:10.1016/S0012-365X(03)00244-910.1016/S0012-365X(03)00244-9Search in Google Scholar

[13] A. Cournier and M. Habib, A new linear algorithm for modular decomposition, in: Trees in Algebra and Programming, S. Tison (Ed(s)), (Springer, 1994) 68–84. doi:10.1007/BFb001747410.1007/BFb0017474Search in Google Scholar

[14] A. Ehrenfeucht, T. Harju and G. Rozenberg, The Theory of 2-Structures, A Framework for Decomposition and Transformation of Graphs (World Scientific, 1999). doi:10.1142/419710.1142/4197Search in Google Scholar

[15] W.J.R. Eplett, Self-converse tournaments, Canad. Math. Bull. 22 (1979) 23–27. doi:10.4153/CMB-1979-004-610.4153/CMB-1979-004-6Search in Google Scholar

[16] R. Fraïssé, Theory of Relations, Revised Edition (North-Holland, 2000).Search in Google Scholar

[17] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66. doi:10.1007/BF0202096110.1007/BF02020961Search in Google Scholar

[18] F. Harary and E. Palmer, On the problem of reconstructing a tournament from subtournaments, Monatsh. Math. 71 (1967) 14–23. doi:10.1007/BF0129995510.1007/BF01299955Search in Google Scholar

[19] P. Ille, La reconstruction des relations binaires, C. R. Acad. Sci. Paris, Sér. I Math. 306 (1988) 635–638.Search in Google Scholar

[20] P. Ille, Recognition problem in reconstruction for decomposable relations, in: Finite and Infinite Combinatorics in Sets and Logic, B. Sands, N. Sauer and R. Woodrow (Ed(s)), (Kluwer Academic Publishers, 1993) 189–198. doi:10.1007/978-94-011-2080-7_1310.1007/978-94-011-2080-7_13Search in Google Scholar

[21] W.M. Kantor, Automorphism groups of designs, Math. Z. 109 (1969) 246–252. doi:10.1007/BF0111140910.1007/BF01111409Search in Google Scholar

[22] W.M. Kantor, Automorphism groups of designs, Math. Z. 109 (1969) 246–252. doi:10.1007/BF0111140910.1007/BF01111409Search in Google Scholar

[23] G. Lopez, Deux résultats concernant la détermination d’une relation par les types d’isomorphie de ses restrictions, C. R. Acad. Sci. Paris, Sér. A-B 274 (1972) 1525–1528.Search in Google Scholar

[24] G. Lopez, L’indéformabilité des relations et multirelations binaires, Z. Math. Logik Grundlag. Math. 24 (1978) 303–317. doi:10.1002/malq.1978024190510.1002/malq.19780241905Search in Google Scholar

[25] G. Lopez and C. Rauzy, Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n − 1), II, Z. Math. Logik Grundlag. Math. 38 (1992) 157–168. doi:10.1002/malq.1992038011110.1002/malq.19920380111Search in Google Scholar

[26] F. Maffray and M. Preissmann, A translation of Tibor Gallai’s paper: Transitiv orientierbare Graphen, in: Perfect Graphs, J.L. Ramirez-Alfonsin and B.A. Reed (Ed(s)), (Wiley, 2001) 25–66.Search in Google Scholar

[27] J.W. Moon, Tournaments whose subtournaments are irreducible or transitive, Canad. Math. Bull. 22 (1979) 75–79. doi:10.4153/CMB-1979-010-710.4153/CMB-1979-010-7Search in Google Scholar

[28] M. Pouzet, Application d’une propriété combinatoire des parties d’un ensemble aux groupes et aux relations, Math. Z. 150 (1976) 117–134. doi:10.1007/BF0121523010.1007/BF01215230Search in Google Scholar

[29] K.B. Reid and C. Thomassen, Strongly self-complementarity and hereditarily isomorphic tournaments, Monatsh. Math. 81 (1976) 291–304. doi:10.1007/BF0138775610.1007/BF01387756Search in Google Scholar

[30] M.Y. Sayar, Partially critical indecomposable tournaments and partially critical supports, Contrib. Discrete Math. 6 (2011) 52–76.Search in Google Scholar

[31] J.H. Schmerl and W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math. 113 (1993) 191–205. doi:10.1016/0012-365X(93)90516-V10.1016/0012-365X(93)90516-VSearch in Google Scholar

[32] J. Spinrad, P4-trees and substitution decomposition, Discrete Appl. Math. 39 (1992) 263–291. doi:10.1016/0166-218X(92)90180-I10.1016/0166-218X(92)90180-ISearch in Google Scholar

[33] P.K. Stockmeyer, The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977) 19–25. doi:10.1002/jgt.319001010810.1002/jgt.3190010108Search in Google Scholar

[34] S.M. Ulam, A Collection of Mathematical Problems (Intersciences Publishers, 1960).Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo