MVLSC HomeΒ β€’Β Issue Contents

Partially Pair-critical Digraphs
Houmem Belkhechine, Jamel Dammak and Rachid Sahbani

Let 𝐺 = (𝑉, 𝐴) be a digraph. For 𝑋 βŠ† 𝑉, the subdigraph of 𝐺 induced by 𝑋 is denoted by 𝐺[𝑋]. A subset 𝑀 of 𝑉 is a module of 𝐺 if for every π‘Ž,𝑏 ∈ 𝑀 and π‘₯ ∈ 𝑉 \ 𝑀, (π‘₯,π‘Ž) ∈ 𝐴 if and only if (π‘₯,𝑏) ∈ 𝐴, and similarly for (π‘Ž, π‘₯) and (𝑏, π‘₯). The trivial modules of 𝐺 are βˆ…, 𝑉 and {π‘₯}, where π‘₯ ∈ 𝑉. The digraph 𝐺 is prime if |𝑉(𝐺)| β©Ύ 3 and all its modules are trivial. Given a prime digraph 𝐺 with a subset 𝑋 of 𝑉 such that |𝑋| β©½ |𝑉 | βˆ’ 4 and 𝐺[𝑋] is prime, the digraph 𝐺 is (partially) pair-critical according to 𝐺[𝑋] if for every π‘₯ ΜΈ= 𝑦 ∈ 𝑉 \ 𝑋, 𝐺[𝑉 \{π‘₯,𝑦}] is non-prime. In this article, we characterize the pair-critical digraphs according to a given prime digraph.

Keywords: Digraph, module, prime, critical pair

2010 MSC: 05C20, 05C75

Full Text (IP)