Geodesic
The {−2,−1}-Selfdual and Decomposable Tournaments
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 743-789.

Voir la notice de l'article provenant de la source Library of Science

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 lt; |X| lt; |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: tournament, decomposable, selfdual 
@article{DMGT_2018_38_3_a8,
     author = {Boudabbous, Youssef and Ille, Pierre},
     title = {The {{\ensuremath{-}2,\ensuremath{-}1}-Selfdual} and {Decomposable} {Tournaments}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {743--789},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a8/}
}
TY  - JOUR
AU  - Boudabbous, Youssef
AU  - Ille, Pierre
TI  - The {−2,−1}-Selfdual and Decomposable Tournaments
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 743
EP  - 789
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a8/
LA  - en
ID  - DMGT_2018_38_3_a8
ER  - 
%0 Journal Article
%A Boudabbous, Youssef
%A Ille, Pierre
%T The {−2,−1}-Selfdual and Decomposable Tournaments
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 743-789
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a8/
%G en
%F DMGT_2018_38_3_a8
Boudabbous, Youssef; Ille, Pierre. The {−2,−1}-Selfdual and Decomposable Tournaments. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 743-789. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a8/

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

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

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

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

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

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

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

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

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

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

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

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

[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/BFb0017474

[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/4197

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

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

[17] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66. doi:10.1007/BF02020961

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

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

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

[21] W.M. Kantor, Automorphism groups of designs, Math. Z. 109 (1969) 246–252. doi:10.1007/BF01111409

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

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

[24] 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.19920380111

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

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

[27] 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/BF01215230

[28] K.B. Reid and C. Thomassen, Strongly self-complementarity and hereditarily isomorphic tournaments, Monatsh. Math. 81 (1976) 291–304. doi:10.1007/BF01387756

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

[30] 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-V

[31] J. Spinrad, P 4 -trees and substitution decomposition, Discrete Appl. Math. 39 (1992) 263–291. doi:10.1016/0166-218X(92)90180-I

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

[33] S.M. Ulam, A Collection of Mathematical Problems (Intersciences Publishers, 1960).