Kernels in circulant digraphs

Document Type: Research Paper

Authors

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

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

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.
Transactions on Combinatorics

Volume 3, Issue 2
June 2014
Pages 45-49

Files

Share

How to cite

Statistics