Description of the minimal prime extension pairs of the $3$-vertex graphs
Abstract
In a graph $G$, a module is a vertex subset $M$ such that every vertex outside $M$ is either adjacent to all or none of $M$. A graph $G$ with at least three vertices is called prime if the empty set, the singleton sets, and the full set of vertices are the only modules in $G$, otherwise $G$ is decomposable. Up to isomorphism, all the $3$-vertex graphs
$K_3, \ \overline{K_3}, P_3, \ and \ \overline{P_3}$ are decomposable.
A prime graph $G$ is $k$-minimal if there is some $k$-element vertex subset $A$ such that each proper induced subgraph of $G$ containing $A$ is decomposable.
In $1998$, A. Cournier and P. Ille described the $1$-minimal and $2$-minimal graphs. Then in $2014$, M. Alzohairi and Y. Boudabbous described the $3$-minimal triangle-free graphs.
In this paper, we describe all $3$-minimal graphs. To do so, we introduce the following notion.
Given a decomposable graph $H$, a minimal prime extension pair of $H$ (or minimal prime $H$-extension pair) is an ordered pair $(G,A)$, where $G$ is a prime graph and $A$ is a vertex subset of $G$ such that $G[A]$ is isomorphic to $H$ and no proper induced subgraph of $G$ containing $A$ is prime. The order of such a pair $(G,A)$ is that of $G$.
Two minimal prime $H$-extension pairs $(G,A)$ and $(G',A')$ are isomorphic if there is an isomorphism $f$ from $G$ onto $G'$ such that
$f(A)=A'$.
For each element $H$ of $\{ K_3, \overline{K_3}, P_3, \overline{P_3}\} $, we describe up to isomorphism the minimal prime $H$-extension pairs and we give,
for each integer $n\geq 4$, the number of nonisomorphic such pairs with order $n$ when $H \in \{P_3, \overline{P_3}\}$.