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.