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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1098,
author = {Mat\'u\v s Harminc and Roman Sot\'ak},
title = {A note on kernels and solutions in digraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {19},
year = {1999},
pages = {237-240},
zbl = {0958.05060},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1098}
}
Matúš Harminc; Roman Soták. A note on kernels and solutions in digraphs. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 237-240. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1098/
[000] [1] M. Behzad and F. Harary, Which directed graphs have a solution?, Math. Slovaca 27 (1977) 37-42. | Zbl 0368.05027
[001] [2] V.V. Belov, E.M. Vorobjov and V.E. Shatalov, Graph Theory (Vyshshaja Shkola, Moskva, 1976). (Russian)
[002] [3] C. Berge, Graphs and Hypergraphs (Dunod, Paris, 1970). (French)
[003] [4] M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). | Zbl 0411.68039
[004] [5] F. Harary, R.Z. Norman and D. Cartwright, Structural Models (John Wiley & Sons, Inc., New York - London - Sydney, 1965). | Zbl 0139.41503
[005] [6] M. Harminc, Kernel and solution numbers of digraphs, Acta Univ. M. Belii 6 (1998) 15-20. | Zbl 0921.05037
[006] [7] M. Harminc and T. Olejnikova, Binary operations on digraphs and solutions, Zb. ved. prac, VST, Košice (1984) 29-42. (Slovak) | Zbl 0586.05018
[007] [8] L. Lovasz, Combinatorial Problems and Exercises (Akademiai Kiado, Budapest, 1979).
[008] [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) | Zbl 0216.02502