Asteroidal Triples of Moplexes
 
 
 

Abstract:

   A moplex is an extremity of a graph, in the same way that a leaf is an extremity of a tree.  We show that we can restrict the definition of asteroidal triple free graphs by using only asteroidal triples of moplexes.
  We define a class of graphs for which any independent set (of size at least three) of moplexes forms an asteroidal set.
  The notion of asteroidal triple of moplexes yields a direct proof of Möhring and Parra's characterization of AT-free graphs ("A graph is AT-free iff every minimal triangulation thereof is an interval graph"), and show how to construct a minimal triangulation which is not an interval graph for any graph which is not AT-free.  We remark how making into a clique some minimal separator of an AT-free graph preserves the property of being AT-free.
  We introduce and characterize a class of linear graphs which includes AT-free graphs.