Kernels in circulant digraphs

Document Type : Research Paper


1 Department of Mathematics, Annamalai University, Annamalainagar 608 002 Tamilnadu.

2 Department of Mathematics, Annamalai University, Annamalainagar 608 002, Tamilnadu


A kernel $J$ of a digraph $D$ is an independent set of vertices of $D$ such that for every vertex $w\,\in\,V(D)\,\setminus\,J$ there exists an arc from $w$ to a vertex in $J.$‎ ‎In this paper‎, ‎among other results‎, ‎a characterization of $2$-regular circulant digraph having a kernel is obtained‎. ‎This characterization is a partial solution to the following problem‎: ‎Characterize circulant digraphs which have kernels; it appeared in the book  Digraphs‎ - ‎theory‎, ‎algorithms and applications‎, ‎Second Edition‎, ‎Springer-Verlag‎, ‎2009‎, ‎by J‎. ‎Bang-Jensen and G‎. ‎Gutin‎.


Main Subjects

J. Bang-Jensen and G. Gutin (2009). Digraphs - theory, algorithms and applications. Second Edition, Springer-Verlag. J. Bang-Jensen, Y. Guo, G. Gutin and L. Volkmann (1997). A classification of locally semi-complete digraphs. Discrete Math.. 167/168, 101-114 M. R. Garey and D. S. Johnson (1979). Computers and intractability. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, Calif.. J. von Neumann and O. Morgenstern (1944). Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ.
  • Receive Date: 02 September 2013
  • Revise Date: 25 January 2014
  • Accept Date: 07 March 2014
  • Published Online: 01 June 2014