Subtournaments isomorphic to $W_{5}$ of an indecomposable tournament
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
We consider a tournament T = (V,A). For each subset X of V is associated the subtournament T(X) = (X,A\(X×X)) of T induced by X. We say that a tournament T0 embeds into a tournament T when T0 is isomorphic to a subtournament of T. Otherwise, we say that T omits T0. A subset X of V is a clan of T provided that for a, b 2 X and x 2 V \X, (a, x) 2 A if and only if (b, x) 2 A. For example, ;, {x}(x 2 V )and V are clans of T, called trivial clans. A tournament is indecomposable if all its clans are trivial. In 2003, B. J. Latka characterized the class T of indecomposable tournaments omitting a certain tournament W5 on 5vertices. In the case of an indecomposable tournament T, we will study the set W5(T) of vertices x 2 V for which there exists a subset X of V such that x 2 X and T(X) is isomorphic to W5. We prove the following:for any indecomposable tournament T, if T 62 T , then |W5(T) ||V | −2and |W5(T) ||V | −1 if |V | is even. By giving examples, we also verify that this statement is optimal.
Abstract
We consider a tournament T = (V,A). For each subset X of V is associated the subtournament T(X) = (X,A\(X×X)) of T induced by X. We say that a tournament T0 embeds into a tournament T when T0 is isomorphic to a subtournament of T. Otherwise, we say that T omits T0. A subset X of V is a clan of T provided that for a, b 2 X and x 2 V \X, (a, x) 2 A if and only if (b, x) 2 A. For example, ;, {x}(x 2 V )and V are clans of T, called trivial clans. A tournament is indecomposable if all its clans are trivial. In 2003, B. J. Latka characterized the class T of indecomposable tournaments omitting a certain tournament W5 on 5vertices. In the case of an indecomposable tournament T, we will study the set W5(T) of vertices x 2 V for which there exists a subset X of V such that x 2 X and T(X) is isomorphic to W5. We prove the following:for any indecomposable tournament T, if T 62 T , then |W5(T) ||V | −2and |W5(T) ||V | −1 if |V | is even. By giving examples, we also verify that this statement is optimal.
참고문헌 (16)
- H. Belkhechine, "Tournois ind´ecomposables et leurs sous-tournois ind´ecomposables a 5 sommets", C. R. Math. Acad. Sci. Paris, 343(11), pp.685~688 (2006)
- H. Belkhechine, "Sous-tournois isomorphes a W5 dans un tournoi ind´ecomposable", C. R. Math. Acad. Sci. Paris, 350(7), pp.333~337 (2012)
- A. Benato, "On an adjacency property of almost all tournaments", Dis- crete Math, 306(19), pp.2327~2335 (2006)
- A. Cournier, "Minimal indecomposable graphs", Discrete Math, 183(1), pp.61~80 (1998)
- H.-D. Ebbinghaus, "Finite Model Theory" (1999), Springer Monographs in Mathematics
- A. Ehrenfeucht, "Primitivity is hereditary for 2-structures", Theoret. Comput. Sci, 70(3), pp.343~358 (1990)
- P. Erdos, "Some remarks on simple tournaments", Algebra Universalis, 2, pp.238~245 (1972)
- R. Fagin, "Probabilities on finite models", J. Symbolic Logic, 41(1), pp.50~58 (1976)
- R. Fagin, "Finite-model theory - a personal perspective", Theoret. Comput. Sci, 116(1), pp.3~31 (1993)
- C. Gnanvo, "La reconstruction des tournois sans diamants", Z. Math. Logik Grundlag. Math, 38(3), pp.283~291 (1992)
- P. Ille, "Indecomposable graphs", Discrete Math, 173(1), pp.71~78 (1997)
- B. J. Latka, "Structure theorem for tournaments omitting N5", J. Graph Theory, 42(3), pp.165~192 (2003)
- G. Lopez, "Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n − 1). I", Z. Math. Logik Grundlag. Math, 38(1), pp.27~37 (1992)
- V. J. Mueller, "Either tournaments or algebras?", Discrete Math, 11, pp.37~66 (1975)
- M. Y. Sayar, "Partially critical tournaments and partially critical supports", Contrib. Discrete Math, 6(1), pp.52~76 (2011)
- J. H. Schmerl, "Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures", Discrete Math, 113(1), pp.191~205 (1993)