Kernels in circulant digraphs

Lakshmi, R.; Vidhyapriya, S.

doi:10.22108/toc.2014.4777

Kernels in circulant digraphs

Document Type : Research Paper

Authors

R. Lakshmi ¹
S. Vidhyapriya ²

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

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

10.22108/toc.2014.4777

Abstract

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‎.

Keywords

Main Subjects

References

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.