Separability Generalizes Dirac's Theorem
 

Abstract:

  In our study of the extremities of a graph, we define a moplex as a maximal clique module the neighborhood of which is a minimal separator of the graph.  This notion enables us to strengthen Dirac's theorem: "Every non-clique triangulated graph has at least two non-adjacent simplicial vertices." by restricting the definition of a simplicial vertex; this also enables us to strengthen Fulkerson& Gross' simplicial elimination scheme, thus providing a new characterization for triangulated graphs.
  Our version of Dirac's theorem generalizes from the class of triangulated graphs to any undirected graph: "Every non-clique graph has at least two non-adjacent moplexes." .
  To insure a linear-time access to a moplex in any graph, we use Rose, Tarjan and Lueker's algorithm for the recognition of triangulated graphs, known as LexBFS: we prove a new algorithmic invariant for this, true even on non-triangulated graphs.
 

Résumé :

  Notre étude des extrémités d'un graphe nous amène à définir la notion de moplex: c'est un module complet maximal dont le voisinage est séparateur minimal du graphe. Cela nous permet de renforcer le théorème de Dirac: "Tout graphe non complet admet au moins deux sommets simpliciaux non-adjacents"  en restreignant la définition de sommet simplicial; de la même façon, cela nous permet de renforcer le schéma d'élimination simplicial défini par Fulkerson et Gross, ce qui fournit une nouvelle caractérisation des graphes triangulés.
  Notre version du théorème de Dirac sur les graphes triangulés se généralise facilement à un graphe quelconque: "Tout graphe non complet admet au moins deux moplex non-adjacents".
  Pour assurer un accès linéaire à un moplex, nous montrons que le célèbre algorithme LexBFS, mis au point par Tarjan et son équipe pour la reconnaissance des graphes triangulés, fournit à la fin de son exécution un moplex dans un graphe tout à fait quelconque.