Recursive construction of the minimal digraphs - Université de La Réunion Accéder directement au contenu
Article Dans Une Revue Journal of Multiple-Valued Logic and Soft Computing Année : 2023

Recursive construction of the minimal digraphs

Moncef Bouaziz
  • Fonction : Auteur
  • PersonId : 944165
Mohammad Alzohari
  • Fonction : Auteur
  • PersonId : 1367744

Résumé

In a digraph $D$, a module is a vertex subset $M$ such that every vertex outside $M$ does not distinguish the vertices in $M$. A digraph $D$ with more than two vertices is prime if $\emptyset$, the single-vertex sets, and $V(D)$ are the only modules in $D$. A prime digraph $D$ is $k$-minimal if there is some $k$-element vertex subset $U$ such that no proper induced subdigraph of $D$ containing $U$ is prime. This concept was introduced by A. Cournier and P. Ille in 1998. They characterized the $1$-minimal and $2$-minimal digraphs. In 2014, M. Alzohairi and Y. Boudabbous described the $3$-minimal triangle-free graphs, and in 2015, M. Alzohairi described a class of $4$-minimal triangle-free graphs. In this paper, we give a recursive procedure to construct the minimal digraphs. More precisely, given an integer $k$, with $k\geq 3$, we give a method for constructing the $k$-minimal digraphs from the $(k-1)$-minimal digraphs.
Fichier non déposé

Dates et versions

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

Licence

Copyright (Tous droits réservés)

Identifiants

  • HAL Id : hal-04520880 , version 1

Citer

Moncef Bouaziz, Mohammad Alzohari, Youssef Boudabbous. Recursive construction of the minimal digraphs. Journal of Multiple-Valued Logic and Soft Computing, 2023, 40, pp.519-539. ⟨hal-04520880⟩
11 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More