K-Kernels in Multipartite Tournaments

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 there exists v ∊ N such that d(u, v) ≤ l). A k-kernel is a (k, k – 1)-kernel. An m-partite tournament is an orientation of an m-partite complete graph. In this paper we use a tool for finding sufficient conditions for a digraph to have a k-kernel, the k-closure of a digraph, which is employed to prove that every m-partite tournament has a k-kernel for every k ≥ 4, m ≥ 2, and to give a simple proof of the fact that for k ≥ 2 it is NP-complete to decide if a digraph D has a k-kernel, or not. We also characterize the m-partite tournaments that have a 3-kernel for m ≥ 2 as those m-partite tournaments having a 2-absorbent vertex for the directed cycles of length four.

Keywords:

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

2010 Mathematics Subject Classification:

• 05C20