MVLSC Home · Issue Contents · Forthcoming Papers
Prime and Critical Digraphs
Mayssam Barhoumi, Jamel Dammak and Hamza Si Kaddour
Given a digraph 𝐺 = (𝑉, 𝐸), a subset 𝑀 of 𝑉 is a module of 𝐺 if for 𝑎 ≠ 𝑏 ∈ 𝑀 and 𝑥 ∈ 𝑉 \ 𝑀, (𝑎, 𝑥) ∈ 𝐸 (resp. (𝑥, 𝑎) ∈ 𝐸) if and only if (𝑏,𝑥) ∈ 𝐸 (resp. (𝑥, 𝑏) ∈ 𝐸). A digraph 𝐺 with at least three vertices is prime if ∅, the singletons and 𝑉 are the only modules of 𝐺. A vertex 𝑥 of a prime digraph 𝐺 is critical if 𝐺 − 𝑥 is not prime. A prime digraph 𝐺 is critical when all its vertices are critical. A prime digraph 𝐺 is {𝑎}- critical if 𝑎 is the only non-critical vertex of 𝐺. P. Ille proved this: Let 𝐺 = (𝑉, 𝐸) be a prime digraph with |𝑉| ≥ 11, for every 𝑥 ∈ 𝑉 there are 𝑦 ≠ 𝑧 ∈ 𝑉 \ {𝑥} such that 𝐺 − {𝑦, 𝑧} is prime. He said that he does not know if his result holds when |𝑉| < 11. We provide an answer to his question by showing that his result can be extended to |𝑉| ∈ {9, 10} but not to |𝑉| = 8. From this, we prove the following: Let 𝐺 = (𝑉, 𝐸) be a prime digraph and 𝑎 ∈ 𝑉. If |𝑉| is odd (resp. even), then 𝐺 is {𝑎}-critical if and only if 𝐺 does not contain any prime digraph of size 8 (resp. 7) containing 𝑎. For this last result, the case of tournaments (respectively symmetric digraphs) was studied by I. Boudabbous (resp. I. Boudabbous, J. Dammak, M. Yaich).
Keywords: Digraph, Graph, Module, Prime digraph, Tournament, Indecomposability
2010 Mathematics Subject Classification: Primary: 05C75; Secondary: 05C20