Groupe d’études et de recherche en analyse des décisions

Cardinalité maximale d’un bistable, distance moyenne dans un graphe, et AutoGraphiX

Rim Kilani

Un stable dans un graphe est un ensemble de sommets deux à deux non adjacents et on note \(\alpha (G)\) le nombre maximum de sommets dans un stable de \(G\). Un bistable dans \(G\) est un sous-graphe induit biparti. Le nombre maximum de sommets dans un bistable de \(G\) est noté \(\alpha_2(G)\). La distance entre deux sommets de \(G\) est le plus petit nombre d’arêtes sur une chaîne reliant ces deux sommets. On note \(\mu(G)\) la moyenne des distances entre toutes les paires de sommets de \(G\). La conjecture 747, générée par ordinateur en 1992, stipule que \(\mu(G) \leq \alpha_2(G)/2\). Il s’agit d’une généralisation d’un résultat de Fan Chung qui dit que \(\mu(G) \leq \alpha(G)\). Pour démontrer la conjecture 747, j’utilise AutoGraphiX2 qui me permet d’obtenir des conjectures, des contres-exemples ou des idées de preuves. Ce logiciel me permet également d’étudier les graphes critiques relativement au bistable maximum (i.e., les graphes \(G\) tel que \(\alpha_2(G - e) > \alpha_2(G)\) pour toute arête \(e\) dans \(G\)).