Recursive Construction of the Minimal Digraphs
Moncef Bouaziz, Mohammad Alzohairi and Youssef Boudabbous
In a digraph 𝐷, a module is a vertex subset 𝑀 such that every vertex outside M does not distinguish the vertices in 𝑀. A digraph 𝐷 with more than two vertices is prime if ∅, the single-vertex sets, and 𝑉(𝐷) are the only modules in 𝐷. A prime digraph 𝐷 is 𝑘-minimal if there is some 𝑘-element vertex subset 𝑈 such that no proper induced subdigraph of 𝐷 containing 𝑈 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 𝑘, with 𝑘 ≥ 3, we give a method for constructing the 𝑘-minimal digraphs from the (𝑘 − 1)-minimal digraphs.
Keywords: Module, prime, isomorphism, minimal digraph
Mathematics Subject Classification: 05C20, 05C60