Open Access   Article Go Back

Kernels in Mycielskian of a Digraph

R. Lakshmi1 , S. Vidhyapriya2

Section:Survey Paper, Product Type: Journal Paper
Volume-7 , Issue-1 , Page no. 560-562, Jan-2019

CrossRef-DOI:   https://doi.org/10.26438/ijcse/v7i1.560562

Online published on Jan 31, 2019

Copyright © R. Lakshmi, S. Vidhyapriya . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

XML View
PDF Download

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: R. Lakshmi, S. Vidhyapriya, “Kernels in Mycielskian of a Digraph,” International Journal of Computer Sciences and Engineering, Vol.7, Issue.1, pp.560-562, 2019.

MLA Style Citation: R. Lakshmi, S. Vidhyapriya "Kernels in Mycielskian of a Digraph." International Journal of Computer Sciences and Engineering 7.1 (2019): 560-562.

APA Style Citation: R. Lakshmi, S. Vidhyapriya, (2019). Kernels in Mycielskian of a Digraph. International Journal of Computer Sciences and Engineering, 7(1), 560-562.

BibTex Style Citation:
@article{Lakshmi_2019,
author = {R. Lakshmi, S. Vidhyapriya},
title = {Kernels in Mycielskian of a Digraph},
journal = {International Journal of Computer Sciences and Engineering},
issue_date = {1 2019},
volume = {7},
Issue = {1},
month = {1},
year = {2019},
issn = {2347-2693},
pages = {560-562},
url = {https://www.ijcseonline.org/full_paper_view.php?paper_id=3542},
doi = {https://doi.org/10.26438/ijcse/v7i1.560562}
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
DO = {https://doi.org/10.26438/ijcse/v7i1.560562}
UR - https://www.ijcseonline.org/full_paper_view.php?paper_id=3542
TI - Kernels in Mycielskian of a Digraph
T2 - International Journal of Computer Sciences and Engineering
AU - R. Lakshmi, S. Vidhyapriya
PY - 2019
DA - 2019/01/31
PB - IJCSE, Indore, INDIA
SP - 560-562
IS - 1
VL - 7
SN - 2347-2693
ER -

VIEWS PDF XML
397 214 downloads 155 downloads
  
  
           

Abstract

A kernel J of a digraph D is an independent set of vertices of D such that for every vertex w∈V(D)J there exists an arc from w to a vertex in J. The Mycielskian μ(D) of a digraph D = (V,A) is the digraph with vertex set V ∪ V^`∪ {u}, where V` = {v`:v ∈ V}, and the arc set A ∪ {(x,y^` ):(x,y)∈ A}∪ {(x^`,y):(x,y)∈ A}∪ {(x`,u):x` ∈ V`} ∪ {(u,x`):x` ∈ V`}. In this paper, we have proved that, for any digraph D, the Mycielskian of D, μ(D), contains a kernel.

Key-Words / Index Term

Kernel, Mycielskian of a digraph

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.