Recursive construction of the minimal digraphs - Université de La Réunion Access content directly
Journal Articles Journal of Multiple-Valued Logic and Soft Computing Year : 2023

Recursive construction of the minimal digraphs

Moncef Bouaziz
  • Function : Author
  • PersonId : 944165
Mohammad Alzohari
  • Function : Author
  • PersonId : 1367744

Abstract

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.
No file

Dates and versions

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

Licence

Copyright

Identifiers

  • HAL Id : hal-04520880 , version 1

Cite

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 View
0 Download

Share

Gmail Mastodon Facebook X LinkedIn More