DMGT

Discussiones Mathematicae Graph Theory 19(2) (1999) 237-240
DOI: https://doi.org/10.7151/dmgt.1098

A NOTE ON KERNELS AND SOLUTIONS IN DIGRAPHS

Matús Harminc

Department of Geometry and Algebra
Faculty of Science, P.J. Safárik University
Jesenná 5, 041 54 Košice, Slovakia
e-mail: harminc@duro.upjs.sk

Roman Soták

Center of applied informatics
Faculty of Science, P.J. Safárik University
Park Angelinum 9, 041 54 Košice, Slovakia

Abstract

For given nonnegative integers k,s an upper bound on the minimum number of vertices of a strongly connected digraph with exactly k kernels and s solutions is presented.

Keywords: kernel of digraph, solution of digraph.

1991 Mathematics Subject Classification: 05C20.

References

[1]	M. Behzad and F. Harary, Which directed graphs have a solution?, Math. Slovaca 27 (1977) 37-42.
[2]	V.V. Belov, E.M. Vorobjov and V.E. Shatalov, Graph Theory (Vyshshaja Shkola, Moskva, 1976). (Russian)
[3]	C. Berge, Graphs and Hypergraphs (Dunod, Paris, 1970). (French)
[4]	M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
[5]	F. Harary, R.Z. Norman and D. Cartwright, Structural Models (John Wiley & Sons, Inc., New York - London - Sydney, 1965).
[6]	M. Harminc, Kernel and solution numbers of digraphs, Acta Univ. M. Belii 6 (1998) 15-20.
[7]	M. Harminc and T. Olejnikova, Binary operations on digraphs and solutions, Zb. ved. prac, VST, Košice (1984) 29-42. (Slovak)
[8]	L. Lovasz, Combinatorial Problems and Exercises (Akademiai Kiado, Budapest, 1979).
[9]	R.G. Nigmatullin, The largest number of kernels in graphs with n vertices, Kazan. Gos. Univ. Ucen. Zap. 130 (1970) kn.3, 75-82. (Russian)

Received 2 February 1999
Revised 29 October 1999