PDF

Discussiones Mathematicae Graph Theory 29(1) (2009) 39-49
DOI: https://doi.org/10.7151/dmgt.1431

k-KERNELS AND SOME OPERATIONS IN DIGRAPHS

Hortensia Galeana-Sanchez Instituto de Matemáticas Universidad Nacional Autónoma de México Ciudad Universitaria, México, D.F. 04510, México

Laura Pastrana Facultad de Ciencias Universidad Nacional Autónoma de México Ciudad Universitaria, Circuito Exterior México, D.F. 04510, México

Abstract

Let D be a digraph. V(D) denotes the set of vertices of D; a set N ⊆ V(D) is said to be a k-kernel of D if it satisfies the following two conditions: for every pair of different vertices u,v ∈ N it holds that every directed path between them has length at least k and for every vertex x ∈ V(D)−N there is a vertex y ∈ N such that there is an xy-directed path of length at most k−1.

In this paper, we consider some operations on digraphs and prove the existence of k-kernels in digraphs formed by these operations from another digraphs.

Keywords: k-kernel, k-subdivision digraph, k-middle digraph and k-total digraph.

2000 Mathematics Subject Classification: Primary: 05C20; Secondary: 05C69.

References

[1]	C. Berge, Graphs (North-Holland Mathematical Library, 6 North Holland, Amsterdam, 1985).
[2]	P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4.
[3]	P. Duchet, A sufficient condition for a digraph to be kernel-perfect, J. Graph Theory 11 (1987) 81-85, doi: 10.1002/jgt.3190110112.
[4]	P. Duchet and H. Meyniel, A note on kernel-critical graphs, Discrete Math. 33 (1981) 103-105, doi: 10.1016/0012-365X(81)90264-8.
[5]	H. Galeana-Sánchez, On the existence of (k,l)-kernels in digraphs, Discrete Math. 85 (1990) 99-102, doi: 10.1016/0012-365X(90)90167-G.
[6]	H. Galeana-Sánchez, On the existence of kernels and h-kernels in directed graphs, Discrete Math. 110 (1992) 251-255, doi: 10.1016/0012-365X(92)90713-P.
[7]	H. Galeana-Sánchez and V. Neumann-Lara, On kernel-perfect critical digraphs, Discrete Math. 59 (1986) 257-265, doi: 10.1016/0012-365X(86)90172-X.
[8]	H. Galeana-Sánchez and V. Neumann-Lara, Extending kernel perfect digraphs to kernel perfect critical digraphs, Discrete Math. 94 (1991) 181-187, doi: 10.1016/0012-365X(91)90023-U.
[9]	M. Harminc, On the (m,n)-basis of a digraph, Math. Slovaca 30 (1980) 401-404.
[10]	M. Harminc, Solutions and kernels of a directed graph, Math. Slovaca 32 (1982) 262-267.
[11]	M. Harminc and T. Olejníková, Binary operations on directed graphs and their solutions (Slovak with English and Russian summaries), Zb. Ved. Pr. VST, Košice (1984) 29-42.
[12]	M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combinatoria 60 (2001) 137-147.
[13]	M. Kucharska and M. Kwaśnik, On (k,l)-kernels of superdigraphs of Pm and Cm, Discuss. Math. Graph Theory 21 (2001) 95-109, doi: 10.7151/dmgt.1135.
[14]	M. Kwaśnik, The generalization of Richardson theorem, Discuss. Math. IV (1981) 11-13.
[15]	M. Kwaśnik, On (k,l)-kernels of exclusive disjunction, Cartesian sum and normal product of two directed graphs, Discuss. Math. V (1982) 29-34.
[16]	M. Blidia, P. Duchet, H. Jacob, F. Maffray and H. Meyniel, Some operations preserving the existence of kernels, Discrete Math. 205 (1999) 211-216, doi: 10.1016/S0012-365X(99)00026-6.
[17]	M. Richardson, Extensions theorems for solutions of irreflexive relations, Proc. Mat. Acad. Sci. 39 (1953) 649-655, doi: 10.1073/pnas.39.7.649.
[18]	M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (1953) 573-590, doi: 10.2307/1969755.
[19]	J. Topp, Kernels of digraphs formed by some unary operations from other digraphs, J. Rostock Math. Kolloq. 21 (1982) 73-81.
[20]	J. von Neumann and O. Morgenstern, Theory of games and economic behavior (Princeton University Press, Princeton, 1944).
[21]	A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301, doi: 10.1016/S0012-365X(96)00064-7.

Received 12 September 2007
Revised 8 December 2007
Accepted 29 December 2008