Header menu link for other important links
X
Acyclic kernel number of oriented cycle related graphs
, B. Rajan, S. Little Joice
Published in
2011
Volume: 79
   
Pages: 111 - 120
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-S there is a vertex v in S, such that (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.
About the journal
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
ISSN08353026