A finiteness theorem for primal extensions

• Published in: Discrete mathematics 2005-06, Vol.296 (1), p.103-116
• Main Author: Zverovich, Igor’
• Format: Article
• Language: English
• Subjects: Combinatorics; Combinatorics. Ordered structures; Exact sciences and technology; Forbidden induced subgraph; Graph theory; Hereditary class; Mathematics; Sciences and techniques of general use; Stability number; Substitutional closure
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2005.01.002

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 then Ext ( G ) is a finite set. We extend this result to a wider class of graphs. A graph is simple if it is isomorphic to an induced subgraph of the path P 4 . Theorem If every homogeneous set of G induces a simple graph then Ext ( G ) is a finite set. We show that our result is best possible in the following sense. Specifically, we prove that for every non-simple graph F there exist a graph G and a homogeneous set W of G such that W induces a subgraph isomorphic to F and Ext ( G ) is infinite.