Total-Kernel in Oriented Circular Ladder and Möbius Ladder

Abstract

A kernel in a directed graph \(D(V, E)\) is a set \(S\) of vertices of \(D\) such that no two vertices in \(S\) are adjacent and for every vertex \(u\) in \(V \setminus S\) there is a vertex \(v\) in \(S\), such that \((u,v)\) is an arc of \(D\). The definition of kernel implies that the vertices in the kernel form an independent set. If the vertices of the kernel induce an independent set of edges, we obtain a variation of the definition of the kernel, namely a total-kernel. The problem of existence of a kernel is itself an NP-complete problem for a general digraph. But in this paper, we solve the strong total-kernel problem of an oriented Circular Ladder and Möbius Ladder in polynomial time.