Acyclic Kernel Number of Oriented Cycle Related Graphs

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 $(\overrightarrow{u,v})$ is an arc of $D$. The problem of existence of a kernel is NP-complete for a general digraph. In this paper, we introduce the acyclic kernel problem for an undirected graph $G$ and solve it in polynomial time for certain cycle-related graphs.