A finiteness theorem for primal extensions (Q2484373): Difference between revisions

A vertex set \(W\) in a graph \(G=(V,E)\) with \(2\leq|W|\leq|V|\) is called homogeneous if every vertex in \(V\setminus W\) is either adjacent to all of the vertices in \(W\) or to none of them. A graph without homogeneous sets is called prime. A prime graph \(H\) is called a primal extension of a graph \(G\) if \(G\) is an induced subgraph of \(H\). A primal extension \(H\) of \(G\) is called minimal if there is no smaller induced subgraph of \(H\) containing \(G\) as an induced subgraph. Let \(\text{Ext}(G)\) denote the set of all minimal primal extensions of \(G\). An interesting problem is the question under which conditions \(\text{Ext} (G)\) is a finite set. This paper extends a sufficient condition found by Giakoumakis in the following way: If every homogeneous set of \(G\) is an induced subgraph of the \(P_4\) (i.e., the induced path with four vertices) then \(\text{Ext}(G)\) is finite.