Description of the minimal prime extension pairs of the $3$-vertex graphs - Université de La Réunion
Journal Articles Journal of Multiple-Valued Logic and Soft Computing Year : 2022

Description of the minimal prime extension pairs of the $3$-vertex graphs

Fatimah Alrusaini
  • Function : Author
  • PersonId : 1367732
Mohammad Alzohairi
  • Function : Author
  • PersonId : 1367733
Moncef Bouaziz
  • Function : Author
  • PersonId : 944165

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}\}$.
No file

Dates and versions

hal-04520821 , version 1 (25-03-2024)

Licence

Copyright

Identifiers

  • HAL Id : hal-04520821 , version 1

Cite

Fatimah Alrusaini, Mohammad Alzohairi, Moncef Bouaziz, Youssef Boudabbous. Description of the minimal prime extension pairs of the $3$-vertex graphs. Journal of Multiple-Valued Logic and Soft Computing, 2022, 39 (2-4), pp.291--340. ⟨hal-04520821⟩
12 View
0 Download

Share

More