Logic/Combinatorics
{1}-self dual finite prechains and applications
Comptes Rendus. Mathématique, Volume 351 (2013) no. 23-24, pp. 859-864.

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 n7 vertices, with at least one neutral pair and for which all the (n1)-subdigraphs are self dual. As an application, we prove that a digraph, on n9 vertices, is hereditarily self dual if and only if all its 4-subdigraphs and its (n3)-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)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)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, à n7 sommets, ayant au moins une paire neutre et dont tous les (n1)-sous-digraphes sont auto duaux. Comme application, nous montrons quʼun digraphe, à n9 sommets, est héréditairement auto dual dès lors que tous ses 4-sous-digraphes et ses (n3)-sous-digraphes sont auto duaux.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2013.10.031
Bouchaala, Houcine 1; Boudabbous, Youssef 2; Lopez, Gérard 3

1 Département de math-physique, Institut préparatoire aux études dʼingénieurs de Sfax, Université de Sfax, B.P. 1172, 3000 Sfax, Tunisia
2 King Saud University, Department of Mathematics, College of Sciences, P. Box 2455, Riyadh 11451, Saudi Arabia
3 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 = {Bouchaala, Houcine and Boudabbous, Youssef and Lopez, G\'erard},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2013.10.031/}
}
TY  - JOUR
AU  - Bouchaala, Houcine
AU  - Boudabbous, Youssef
AU  - Lopez, Gérard
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2013.10.031/
DO  - 10.1016/j.crma.2013.10.031
LA  - en
ID  - CRMATH_2013__351_23-24_859_0
ER  - 
%0 Journal Article
%A Bouchaala, Houcine
%A Boudabbous, Youssef
%A Lopez, Gérard
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2013.10.031/
%R 10.1016/j.crma.2013.10.031
%G en
%F CRMATH_2013__351_23-24_859_0
Bouchaala, Houcine; Boudabbous, Youssef; Lopez, Gérard. $ \{-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. http://www.numdam.org/articles/10.1016/j.crma.2013.10.031/

[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 (n1), 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 (n1), 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

Cited by Sources: