Download PDF - A note on kernels and solutions in digraphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

A note on kernels and solutions in digraphs

Authors 1, 2

Affiliations

  1. Department of Geometry and Algebra, Faculty of Science, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovakia
  2. Center of applied informatics, Faculty of Science, P.J. Šafá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

ENG
kernel of digraph, solution of digraph

Bibliography

  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)
Discussiones Mathematicae Graph Theory
1999/19/2
Export to PBN, Opens in new tab
Pages:
237-240
Main language of publication
English
Received
1999-02-02
Accepted
1999-10-29
Published
1999

DOI: 10.7151/dmgt.1098

Exact and natural sciences