Description of the Minimal Prime Extension Pairs of the 3-vertex Graphs
Fatimah Alrusaini, Mohammad Alzohairi, Moncef Bouaziz and Youssef Boudabbous
In a graph 𝐺, a module is a vertex subset 𝑀 such that every vertex outside 𝑀 is either adjacent to all or none of 𝑀. A graph 𝐺 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 𝐺, otherwise 𝐺 is decomposable. Up to isomorphism, all the 3-vertex graphs 𝐾3, 𝐾3, 𝑃3, and 𝑃3 are decomposable.
A prime graph 𝐺 is 𝑘-minimal if there is some 𝑘-element vertex subset 𝐴 such that each proper induced subgraph of 𝐺 containing 𝐴 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 𝐻, a minimal prime extension pair of 𝐻 (or minimal prime 𝐻-extension pair) is an ordered pair (𝐺, 𝐴), where 𝐺 is a prime graph and 𝐴 is a vertex subset of 𝐺 such that 𝐺[𝐴] is isomorphic to 𝐻 and no proper induced subgraph of 𝐺 containing 𝐴 is prime. The order of such a pair (𝐺, 𝐴) is that of 𝐺. Two minimal prime 𝐻-extension pairs (𝐺, 𝐴) and (𝐺’, 𝐴’) are isomorphic if there is an isomorphism 𝑓 from 𝐺 onto 𝐺’ such that 𝑓 (𝐴) = 𝐴’.
For each element 𝐻 of {𝐾3, 𝐾3,, 𝑃3, 𝑃3}, we describe up to isomorphism the minimal prime 𝐻-extension pairs and we give, for each integer 𝑛 ≥ 4, the number of nonisomorphic such pairs with order 𝑛 when 𝐻 ∈ {𝑃3, 𝑃3}.
Keywords: Module, Prime, Isomorphism, Minimal graph, Minimal prime extension pair, Chain