Acyclic Kernel Number of Oriented Cycle Related Graphs

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 \( (\overline{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.