A finiteness theorem for primal extensions

A set W⊆V(G) is called homogeneous in a graph G if 2?|W|?|V(G)|-1, and N(x)?W=N(y)?W for each x,y∈W. A graph without homogeneous sets is called prime. A graph H is called a (primal) extension of a graph G if G is an induced subgraph of H, and H is a prime graph. An extension H of G is minimal if there are no extensions of G in the set ISub(H)?{H}. We denote by Ext(G) the set of all minimal extensions of a graph G.We investigate the following problem: find conditions under which Ext(G) is a finite set. The main result of Giakoumakis (Discrete Math. 177 (1997) 83-97) is the following sufficient condition.

Theorem. If every homogeneous set of G has exactly two vertices thenExt(G)is a finite set.