$ \{-1\}$-self dual finite prechains and applications

Houcine Bouchaala; Youssef Boudabbous; Gérard Lopez

doi:10.1016/j.crma.2013.10.031

Logic/Combinatorics

{- 1}

-self dual finite prechains and applications

Presented by: the Editorial Board

Houcine Bouchaala ¹; Youssef Boudabbous ²; Gérard Lopez ³

¹ Département de math-physique, Institut préparatoire aux études dʼingénieurs de Sfax, Université de Sfax, B.P. 1172, 3000 Sfax, Tunisia
² King Saud University, Department of Mathematics, College of Sciences, P. Box 2455, Riyadh 11451, Saudi Arabia
³ Institut de mathématiques de Luminy, CNRS–UPR 9016, 163 avenue de Luminy, case 907, 13288, Marseille cedex 09, France

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

Abstract
Résumé

Given a digraph $D = (V, A)$ , a pair ${x, y}$ of distinct vertices of D is neutral if $(x, y) \in A \Leftrightarrow (y, x) \in 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) \in 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.

Étant donné un digraphe $D = (V, A)$ , une paire ${x, y}$ de sommets de D distincts est neutre si $(x, y) \in A \Leftrightarrow (y, x) \in 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) \in 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.

Received: 2013-08-10
Accepted: 2013-10-25
Published online: 2013-11-21

DOI: 10.1016/j.crma.2013.10.031

Author's affiliations:

Houcine Bouchaala ¹; Youssef Boudabbous ²; Gérard Lopez ³

¹ Département de math-physique, Institut préparatoire aux études dʼingénieurs de Sfax, Université de Sfax, B.P. 1172, 3000 Sfax, Tunisia
² King Saud University, Department of Mathematics, College of Sciences, P. Box 2455, Riyadh 11451, Saudi Arabia
³ Institut de mathématiques de Luminy, CNRS–UPR 9016, 163 avenue de Luminy, case 907, 13288, Marseille cedex 09, France

@article{CRMATH_2013__351_23-24_859_0,
     author = {Houcine Bouchaala and Youssef Boudabbous and G\'erard Lopez},
     title = {$ \{-1\}$-self dual finite prechains and applications},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {859--864},
     publisher = {Elsevier},
     volume = {351},
     number = {23-24},
     year = {2013},
     doi = {10.1016/j.crma.2013.10.031},
     language = {en},
}

TY  - JOUR
AU  - Houcine Bouchaala
AU  - Youssef Boudabbous
AU  - Gérard Lopez
TI  - $ \{-1\}$-self dual finite prechains and applications
JO  - Comptes Rendus. Mathématique
PY  - 2013
SP  - 859
EP  - 864
VL  - 351
IS  - 23-24
PB  - Elsevier
DO  - 10.1016/j.crma.2013.10.031
LA  - en
ID  - CRMATH_2013__351_23-24_859_0
ER  -

%0 Journal Article
%A Houcine Bouchaala
%A Youssef Boudabbous
%A Gérard Lopez
%T $ \{-1\}$-self dual finite prechains and applications
%J Comptes Rendus. Mathématique
%D 2013
%P 859-864
%V 351
%N 23-24
%I Elsevier
%R 10.1016/j.crma.2013.10.031
%G en
%F CRMATH_2013__351_23-24_859_0

Houcine Bouchaala; Youssef Boudabbous; Gérard Lopez. $ \{-1\}$-self dual finite prechains and applications. Comptes Rendus. Mathématique, Volume 351 (2013) no. 23-24, pp. 859-864. doi : 10.1016/j.crma.2013.10.031. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2013.10.031/

References
Cited by

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

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

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

[4] H. Bouchaala; Y. Boudabbous 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] Y. Boudabbous Sur la détermination dʼune relation binaire à partir dʼinformations locales, Math. Logic Quart., Volume 44 (1998), pp. 265-276

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

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

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

[9] G. Lopez; C. Rauzy 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] G. Lopez; C. Rauzy 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] M. Pouzet 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] S.M. Ulam (Interscience Tracts in Pure and Appl. Math.), Intrescience Publishers, Groningen, New York (1960), p. 29

Cited by Sources:

Comments - Policy