[Graphs critically without duo]
Let be a digraph. G is a tournament if for , if and only if . The induced subgraph of G by a subset X of V is denoted by . A subset I of V is an interval of G provided that for any and , if and only if , and if and only if . An interval of G on 2 elements is called duo of G. G is called critically without duo if it is without duo and for all , the subgraph has at least one duo. Following the study of acyclic tournaments made by J.F. Culus and B. Jouve in 2005, we give, in this Note, a complete morphologic description of critically without duo graphs.
Soit un graphe (orienté). Le graphe G est un tournoi si pour , si et seulement si . À chaque partie X de S est associé le sous-graphe de G induit par X. Une partie I de S est un intervalle de G si pour tous et , si et seulement si et si et seulement si . Un duo de G est un intervalle de G à deux éléments. Le graphe G est critiquement sans duo s'il est sans duo et si pour tout , le sous-graphe admet au moins un duo. Suite à l'étude des tournois acycliques, faite par J.F. Culus et B. Jouve en 2005, nous donnons, dans cette Note, une description morphologique complète des graphes critiquement sans duo.
Accepted:
Published online:
Youssef Boudabbous 1; Abdeljelil Salhi 2
@article{CRMATH_2009__347_9-10_463_0, author = {Youssef Boudabbous and Abdeljelil Salhi}, title = {Les graphes critiquement sans duo}, journal = {Comptes Rendus. Math\'ematique}, pages = {463--466}, publisher = {Elsevier}, volume = {347}, number = {9-10}, year = {2009}, doi = {10.1016/j.crma.2009.03.008}, language = {fr}, }
Youssef Boudabbous; Abdeljelil Salhi. Les graphes critiquement sans duo. Comptes Rendus. Mathématique, Volume 347 (2009) no. 9-10, pp. 463-466. doi : 10.1016/j.crma.2009.03.008. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2009.03.008/
[1] J.L. Beauvois, G. Lopez, Un opérateur de densification d'un graphe. Le graphe des parentés, Soumis, 2008
[2] Y. Boudabbous, P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, Discrete Math. (2008), in press
[3] Tournois sans intervalle acyclique, C. R. Acad. Sci. Paris, Ser. I, Volume 341 (2005), pp. 465-468
[4] Abritement entre relations et spécialement entre chaînes, Symposi. Math., Instituto Nazionale di Alta Matematica, Volume 5 (1970), pp. 203-251
[5] Indecomposable graphs, Discrete Math., Volume 173 (1997), pp. 71-78
[6] Critically indecomposable partially ordered sets, graphs, tounaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205
Cited by Sources:
Comments - Policy