Minimal Duo-free Digraphs for One or Two Vertices
Nesrine Azizi, Imed Boudabbous and Abdeljelil Salhi
Let 𝐺 be a digraph. A subset 𝑋 of 𝑉(𝐺) is a module of 𝐺 provided that for any 𝑎, 𝑏 ∈ 𝑋 and 𝑥 ∈ 𝑉(𝐺) \ 𝑋, (𝑎, 𝑥) ∈ 𝐸(𝐺) if and only if (𝑏, 𝑥) ∈ 𝐸(𝐺) and (𝑥, 𝑎) ∈ 𝐸(𝐺) if and only if (𝑥, 𝑏) ∈ 𝐸(𝐺). For instance, ∅, {𝑥} where 𝑥 ∈ 𝑉(𝐺) and 𝑉(𝐺) are modules of 𝐺, called trivial modules. A 2-element module of 𝐺 is called a duo of 𝐺. The digraphs which do not admit any duo are called duo-free digraphs. We introduce the duo-free-minimal digraphs in the following way: Given a duo-free digraph 𝐺 and vertices 𝑥1, …, 𝑥𝑘 of 𝐺, 𝐺 is said to be duo-free-minimal for 𝑥1, …, 𝑥𝑘 when for each proper subset 𝑋 of 𝑉(𝐺) containing 𝑥1, …, 𝑥𝑘 , 𝐺[𝑋] has at least one duo. In this paper, we characterize the duo-free-minimal tournaments and graphs for one or two vertices.
Keywords: Module, duo, duo-free-minimal graph
MSC (2020): 05C20, 05C51, 05C60