Kernels in Mycielskian of a Digraph

Authors

  • Lakshmi R Dept. of Mathematics, Dharumapuram Gnanambigai Government Arts College for Women, Mayiladuthurai 609 001, India
  • Vidhyapriya S Dept. of Mathematics, Dharumapuram Gnanambigai Government Arts College for Women, Mayiladuthurai 609 001, India

DOI:

https://doi.org/10.26438/ijcse/v7i1.560562

Keywords:

Kernel, Mycielskian of a digraph

Abstract

A kernel of a digraph is an independent set of vertices of such that for every vertex there exists an arc from to a vertex in The Mycielskian of a digraph is the digraph with vertex set where and the arc set In this paper, we have proved that, for any digraph D, the Mycielskian of contains a kernel.

References

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Second Edition, Springer-Verlag, 2009.

[2] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, NJ, 1944.

[3] M. R. Garey and D. S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freemann and Co., San Francisco, Calif., 1979.

[4] E. Boros, V. Gurvich, Perfect graphs, kernels, and cores of cooperative games, Discrete Math. 306 (2006) 2336–2354.

[5] M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (2) (1953) 573–580.

[6] M. Richardson, Extensions theorems for solutions of irreflexive relations, Proc. Natl. Acad. Sci. USA 39 (1953) 649–651.

[7] P. Duchet, H. Meyniel, A note on kernel–critical graphs, Discrete Math. 33 (1981) 103–105.

[8] P. Duchet, Graphes Noyau-Parfaits, Ann. Discrete Math. 9 (1980) 93–101.

[9] P. Duchet, A sufficient condition for a digraph to be kernel- perfect, J. Graph Theory 11 (1) (1987) 81–85.

[10] H. Galeana-Sánchez, R. Rojas-Monroy, Kernels in quasi- transitive digraphs, Discrete Math. 306 (2006) 1969–1974.

[11] H. Galeana-Sánchez, V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67–76.

[12] Litao Guo and Xiaofeng Guo, Connectivity of the Mycielskian of a digraph, Applied Mathematics Letters, 22 (2009) 1622-1625.

Downloads

Published

2019-01-31
CITATION
DOI: 10.26438/ijcse/v7i1.560562
Published: 2019-01-31

How to Cite

[1]
R. Lakshmi and S. Vidhyapriya, “Kernels in Mycielskian of a Digraph”, Int. J. Comp. Sci. Eng., vol. 7, no. 1, pp. 560–562, Jan. 2019.

Issue

Vol. 7 No. 1 (2019): IJCSE January Edition

Section

Survey Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.