On the Number of Non-Critical Vertices in Prime Graphs

Source abstract

Let G=(V,E) be a finite simple graph. A module of G is a subset M⊆V such that every vertex in V∖M is adjacent either to all vertices of M or to none of them. The sets ∅, V, and the singletons of V are called the trivial modules of G. The graph G is decomposable if it has a non-trivial module; otherwise, it is indecomposable The graph G is prime if it is indecomposable and has at least four vertices. A vertex x of a prime graph G is critical if the induced subgraph G−x is decomposable. We give a complete answer to the following existence problem: for which integers n and k does there exist a prime graph on n vertices with exactly k non-critical vertices? Our first main result shows that, for all integers n≥8 and 2≤k≤n, such a graph exists and can be chosen to be triangle-free; for k=1, a triangle-free example exists if and only if n is even. Our second main result states that, for all integers n≥6 and 1≤k≤n, such a graph exists. Both bounds n≥8 and n≥6 are tight. Together with the classical result of Schmerl and Trotter for k=0, this settles the existence problem. All proofs are constructive: the required graphs are built explicitly by means of modular decomposition.