HEREDITARY HEMIMORPHY OF {-k}-HEMIMORPHIC TOURNAMENTS FOR k ≥ 5
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let T = (V,A) be a tournament. With every subset X of V is associated the subtournament T[X] = (X,A ∩ (X ×X)) of T, induced by X. The dual of T, denoted by T*, is the tournament obtained from T by reversing all its arcs. Given a tournament T'=(V,A') and a nonnegative integer k, T and T' are {-k}-hemimorphic provided that for all X ⊂ V , with │X│= k, T[V-X] and T'[V-X] or T*[V-X] and T'[V-X]are isomorphic. The tournaments T and T' are said to be hereditarily hemimorphic if for all subset X of V , the subtournaments T[X] and T'[X]are hemimorphic. The purpose of this paper is to establish the hereditary hemimorphy of the {-k}-hemimorphic tournaments on at least k + 7vertices, for every k ≥ 5.
Abstract
Let T = (V,A) be a tournament. With every subset X of V is associated the subtournament T[X] = (X,A ∩ (X ×X)) of T, induced by X. The dual of T, denoted by T*, is the tournament obtained from T by reversing all its arcs. Given a tournament T'=(V,A') and a nonnegative integer k, T and T' are {-k}-hemimorphic provided that for all X ⊂ V , with │X│= k, T[V-X] and T'[V-X] or T*[V-X] and T'[V-X]are isomorphic. The tournaments T and T' are said to be hereditarily hemimorphic if for all subset X of V , the subtournaments T[X] and T'[X]are hemimorphic. The purpose of this paper is to establish the hereditary hemimorphy of the {-k}-hemimorphic tournaments on at least k + 7vertices, for every k ≥ 5.
참고문헌 (23)
- J. A. Bondy, "A graph reconstructor's manual, Surveys in combinatorics", London Math. Soc. Lecture Note Ser, 166, pp.221~252 (1991), Cambridge Univ. Press
- J. A. Bondy, "Graph reconstruction-a survey", J. Graph Theory, 1(3), pp.227~268 (1977)
- M. Bouaziz, "La demi-isomorphie et les tournois fortement connexes nis", C. R. Math. Acad. Sci. Paris, 335(2), pp.105~110 (2002)
- H. Bouchaala, "La {-k}-autodualite des sommes lexicographiques nies de tournois suivant un 3-cycle ou un tournoi critique", Ars Combin, 81, pp.33~64 (2006)
- Y. Boudabbous, "Isomorphie hereditaire et {-4}-hypomorphie pour les tournois", C. R. Math. Acad. Sci. Paris, 347(15), pp.841~844 (2009)
- Y. Boudabbous, "Sur la (-k)-demi-reconstructibilite des tournois nis", C. R. Acad. Sci. Paris Ser. I Math, 326(9), pp.1037~1040 (1998)
- Y. Boudabbous, "La relation difference et l'anti-isomorphie", Math. Logic Quart, 41(2), pp.268~280 (1995)
- A. Boussairi, "The C3-structure of the tournaments", Discrete Math, 277(1), pp.29~43 (2004)
- A. Ehrenfeucht, "Primitivity is hereditary for 2-structures", Theoret. Comput. Sci, 70(3), pp.343~358 (1990)
- R. Fraisse, "Abritement entre relations et specialement entre cha^ines, Symposia Mathematica, Vol. V", pp.203~251 (1971), Academic Press
- T. Gallai, "Transitiv orientierbare Graphen", Acta Math. Acad. Sci. Hungar, 18, pp.25~66 (1967)
- C. Gnanvo, "La reconstructibilite des tournois", C. R. Acad. Sci. Paris Ser. I Math, 306(14), pp.577~580 (1988)
- J. G. Hagendorf, "La demi-reconstructibilite des relations binaires d'au moins 13 elements", C. R. Acad. Sci. Paris Ser. I Math, 317(1), pp.7~12 (1993)
- P. Ille, "La reconstructibilite des relations binaires", C. R. Acad. Sci. Paris Ser. I Math, 306(15), pp.635~638 (1988)
- G. Lopez, "Deux resultats concernant la determination d'une relation par les types d'isomorphie de ses restrictions", C. R. Acad. Sci. Paris Ser. A-B, 274, pp.1525~1528 (1972)
- G. Lopez, "Sur la determination d'une relation par les types d'isomorphie de ses restric- tions", C. R. Acad. Sci. Paris Ser. A-B, 275, pp.951~953 (1972)
- G. Lopez, "L'indeformabilite des relations et multirelations binaires", Z. Math. Logik Grundlag. Math, 24(4), pp.303~317 (1978)
- 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)
- G. Lopez, "Reconstruction of binary relations from their restrictions of cardinality 2; 3; 4 and (n 1). II, Z. Math", Logik Grundlag. Math, 38(2), pp.157~168 (1992)
- J. W. Moon, "Topic on Tournaments" (1968), Holt, Rinehart and Winston
- M. Pouzet, "Application d'une propriete combinatoire des parties d'un ensemble aux groupes et aux relations", Math. Z, 150(2), pp.117~134 (1976)
- M. Pouzet, "Relations non reconstructibles par leurs restrictions", J. Combin. Theory Ser. B, 26(1), pp.22~34 (1979)
- K. B. Reid, "Strongly self-complementary and hereditarily isomorphic tournaments", Monatsh. Math, 81(4), pp.291~304 (1976)