{−1}-self dual finite prechains and applications

Bouchaala, Houcine; Boudabbous, Youssef; Lopez, Gérard

Comptes Rendus. Mathématique, Tome 351 (2013) no. 23-24, pp. 859-864.

Étant donné un digraphe D=(V,A), une paire {x,y} de sommets de D distincts est neutre si (x,y)∈A⇔(y,x)∈A. Un k-sous-digraphe de D est un sous-digraphe induit de D ayant k sommets. Le dual de D est le digraphe D⋆=(V,A⋆) où A⋆={(x,y);(y,x)∈A}. Un digraphe est auto dual sʼil est isomorphe à son dual. Il est héréditairement auto dual si tous ses sous-digraphes induits sont auto duaux. Un digraphe est une préchaîne sʼil nʼa aucun 3-sous-digraphe non auto dual ayant exactement une paire neutre, aucun 3-sous-digraphe ayant au moins deux paires neutres, aucun 4-sous-digraphe non auto dual sans paire neutre. Dans cette note, nous décrivons les préchaînes, à n⩾7 sommets, ayant au moins une paire neutre et dont tous les (n−1)-sous-digraphes sont auto duaux. Comme application, nous montrons quʼun digraphe, à n⩾9 sommets, est héréditairement auto dual dès lors que tous ses 4-sous-digraphes et ses (n−3)-sous-digraphes sont auto duaux.

Given a digraph D=(V,A), a pair {x,y} of distinct vertices of D is neutral if (x,y)∈A⇔(y,x)∈A. A k-subdigraph of D is an induced subdigraph of D with k vertices. The dual of D is the digraph D⋆=(V,A⋆), where A⋆={(x,y);(y,x)∈A}. D is self dual if it is isomorphic to its dual. It is hereditarily self dual if each one of its induced subdigraphs is self dual. A digraph is a prechain if it has neither any non self dual 3-subdigraph with exactly one neutral pair, nor any 3-subdigraph with at least two neutral pairs, nor any non self dual 4-subdigraph with no neutral pair. In this note, we describe the prechains, on n⩾7 vertices, with at least one neutral pair and for which all the (n−1)-subdigraphs are self dual. As an application, we prove that a digraph, on n⩾9 vertices, is hereditarily self dual if and only if all its 4-subdigraphs and its (n−3)-subdigraphs are self dual.

[1] Basso-Gerbelli, M.; Ille, P. La reconstruction des relations définies par interdits, C. R. Acad. Sci. Paris, Ser. I, Volume 316 (1993), pp. 1229-1234

[2] Bondy, J.-A. A graph reconstructorʼs manual (Keendwell, A.D., ed.), Surveys Combinatorics, London Mathematical Society Lecture Note Series, vol. 166, Cambridge University Press, 1991, pp. 221-252

[3] Bondy, J.A.; Hemminger, R.L. Graph reconstruction, a survey, J. Graph Theory (1977), pp. 227-268

[4] Bouchaala, H.; Boudabbous, Y. La {−k}-autodualité des sommes lexicographiques finies de tournois suivant un 3-cycle ou un tournoi critique, Ars Combin., Volume 81 (2006), pp. 33-64

[5] Boudabbous, Y. Sur la détermination dʼune relation binaire à partir dʼinformations locales, Math. Logic Quart., Volume 44 (1998), pp. 265-276

[6] Boudabbous, Y.; Delhommé, C. Prechains and self duality, Discrete Math., Volume 312 (2012), pp. 1743-1765

[7] Boussaïri, A. Communication personnelle à Y. Boudabbous, 1995

[8] Fraïssé, R. Lʼintervalle en théorie des relations, ses généralisations, filtre intervallaire et clôture dʼune relation (Pouzet, M.; Richard, D., eds.), Orders, Description and Roles, North-Holland, 1984, pp. 313-342

[9] Lopez, G.; Rauzy, C. Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n−1), I, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 27-37

[10] Lopez, G.; Rauzy, C. Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n−1), II, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 157-168

[11] Pouzet, M. Application dʼune propriété combinatoire des parties dʼun ensemble aux groupes et aux relations, Math. Z., Volume 150 (1976), pp. 117-134

[12] Ulam, S.M. (Interscience Tracts in Pure and Appl. Math.), Intrescience Publishers, Groningen, New York (1960), p. 29