Ensembles indépendants maximum / maximum

26

Existe-t-il quelque chose de connu sur la classe des graphes avec la propriété que tous les ensembles indépendants maximaux ont la même cardinalité et sont donc des IS maximum?

Par exemple, prenez un ensemble de points dans le plan et considérez le graphique des intersections entre tous les segments entre les paires de points de l'ensemble. (segments-> sommets, intersections-> arêtes). Ce graphique aura la propriété ci-dessus, car tous les IS maximaux correspondent à des triangulations de l'ensemble de points d'origine. Existe-t-il d'autres catégories de graphiques possédant cette propriété? Cette propriété peut-elle être facilement testée?

László Kozma
la source
7
Il y a un article connexe ici ( portal.acm.org/citation.cfm?id=303085 ) qui suggère que le problème de déterminer cela pour un graphique donné est co-NP-complet, et donc caractériser la propriété sera délicat
Suresh Venkat

Réponses:

26

Ces graphiques sont appelés graphiques bien couverts . Voici un article récent sur le sujet qui énumère plusieurs références utiles. Comme Suresh l'a mentionné, le problème de reconnaissance est co-NP-complet.

Notez que les ensembles indépendants d'un graphe forment un complexe simplicial abstrait. Les complexes simpliciaux qui surgissent de cette manière sont appelés «complexes d'indépendance» ou «complexes de drapeaux». Un complexe simplicial est dit pur si chaque simplexe maximal a la même cardinalité. Vous pouvez donc trouver des articles pertinents en recherchant «complexe d'indépendance pure» ou «complexe de drapeau pur».

Timothy Chow
la source
Merci, c'est exactement ce que je cherchais. À la recherche de «graphiques bien couverts», j'ai trouvé de nombreuses autres références.
László Kozma
7

La propriété MAXIMAL = MAXIMUM pour les ensembles indépendants dans les graphiques et les structures combinatoires plus générales est importante. Il sera intéressant de comprendre les graphiques où cette propriété est valable pour tous les sous-graphiques induits. Un cas abstrait général où nous avons MAXIMUM = MAXIMAL est quand il y a une structure matroïde sous-jacente, mais il y a beaucoup d'autres cas, comme le cas des graphes planaires maximaux mentionnés dans la question. Voici un exemple connexe: considérons n points dans le plan en position convexe et soit k un entier. Considérez les graphiques dont les sommets sont des segments de ligne entre ces points où deux sommets sont adjacents si les segments de ligne ne se croisent pas. La robe a prouvé que pour ce graphique MAXIMIM = MAXIMAL pour les ensembles indépendants.

Gil Kalai
la source
6
"Il sera intéressant de comprendre les graphes où cette propriété est valable pour tous les sous-graphes induits". Sauf erreur, un graphe (connecté) et chacun de ses sous-graphes induits sont bien couverts si ce n'est un graphe complet, car le chemin avec 3 sommets et 2 arêtes n'est pas bien couvert. P3
user13136