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