Two novel results on the existence of 3-kernels in digraphs
share
Let D be a digraph. We call a subset N of V(D)k-independent if for every pair of vertices u,v ∈ N, d(u,v) ≥ k; and we call it ℓ-absorbent if for every vertex u ∈ V(D) ∖ N, there exists v ∈ N such that d(u,v) ≤ℓ. A (k,ℓ)-kernel of D is a subset of vertices which is k-independent and ℓ-absorbent. A k-kernel is a (k,k-1)-kernel. In this report, we present the main results from our master's research regarding kernel theory. We prove that if a digraph D is strongly connected and every cycle C of D satisfies: (i) if C ≡ 0 3, then C has a short chord and (ii) if C ≢0 3, then C has three short chords: two consecutive and a third crossing one of the former, then D has a 3-kernel. Moreover, we introduce a modification of the substitution method, proposed by Meyniel and Duchet in 1983, for 3-kernels and use it to prove that a quasi-3-kernel-perfect digraph D is 3-kernel-perfect if every circuit of length not dividable by three has four short chords.
READ FULL TEXT