On the existence of k-kernels in digraphs and in weighted digraphs

Abstract

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.

A (k, l)-kernel N of D is a k-independent set of vertices (if u, v ∊ N then d(u, v), d(v, u) ≥ k) and l-absorbent (if u ∊ V(D) \ N then exists v ∊ N such that d(u, v) ≤ l). A k-kernel is a (k, k - 1)-kernel. We propose an extension of the definition of (k, l)-kernel to (arc-) weighted digraphs, verifying which of the existing results for k-kernels are valid in this extension. If D is a digraph and w: A(D) → Z is a weight function for the arcs of D, we can restate the problem of finding a k-kernel in the following way. If 풞 is a walk in D, the weight of 풞 is defined as . A subset S ⊆ V(D) is (k, w)-independent if, for every u, v ∊ S there does not exist an uv-directed path of weight less than k. A subset S ⊆ V(D) will be (l, w)-absorbent if, for every u ⊆ V(D) \ S, there exists an uS-directed path of weight less than or equal to l. A subset N ⊆ V(D) is a (k, l, w)-kernel if it is (k, w)-independent and (l, w)-absorbent. We prove, among other results, that every transitive digraph has a (k, k - l, w)-kernel for every k, that if T is a tournament and for every a ⊆ A(T), then T has a (k, w)-kernel and that if every directed cycle in a quasi-transitive digraph D has weight ≤ , then D has a (k, w)-kernel.

Also, we let the weight function to have an arbitrary group as codomain and propose another variation of the concept of k-kernel.

Keywords:

• digraph
• kernel
• (k, l)-kernel
• k-kernel

2010 Mathematics Subject Classification:

• 05C20