All minimal prime extensions of hereditary classes of graphs
The substitution composition of two disjoint graphs G(1) and G(2) is obtained by first removing a vertex x from G(2) and then making every vertex in G(1) adjacent to all neighbours of x in G(2). Let F be a family of graphs defined by a set Z of forbidden configurations. Giakoumakis [V. Giakoumakis, On the closure of graphs under substitution, Discrete Mathematics 177 (1997) 83-97] proved that F*, the closure under substitution of F, can be characterized by a set Z* of forbidden configurations the minimal prime extensions of Z. He also showed that Z* is not necessarily a finite set. Since substitution preserves many of the properties of the composed graphs, an important problem is the following: find necessary and sufficient conditions for the finiteness of Z*. Giakoumakis [V. Giakoumakis, On the closure of graphs under substitution, Discrete Mathematics 177 (1997) 83-97] presented a sufficient condition for the finiteness of Z* and a simple method for enumerating all its elements. Since then, many other researchers have studied various classes of graphs for which the substitution closure can be characterized by a finite set of forbidden configurations. The main contribution of this paper is to completely solve the above problem by characterizing all classes of graphs having a finite number of minimal prime extensions. We then go on to point out a simple way for generating an infinite number of minimal prime extensions for all the other classes of F*. (c) 2006 Elsevier B.V. All rights reserved.
graph theory graph decompositions modular decomposition