A note on kernels and solutions in digraphs

Matúš Harminc; Roman Soták

Discussiones Mathematicae Graph Theory (1999)

  • Volume: 19, Issue: 2, page 237-240
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Matúš Harminc, and Roman Soták. "A note on kernels and solutions in digraphs." Discussiones Mathematicae Graph Theory 19.2 (1999): 237-240. <http://eudml.org/doc/270700>.

@article{MatúšHarminc1999,
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.},
author = {Matúš Harminc, Roman Soták},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel of digraph; solution of digraph; strongly connected digraph; kernels},
language = {eng},
number = {2},
pages = {237-240},
title = {A note on kernels and solutions in digraphs},
url = {http://eudml.org/doc/270700},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Matúš Harminc
AU - Roman Soták
TI - A note on kernels and solutions in digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 2
SP - 237
EP - 240
AB - 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.
LA - eng
KW - kernel of digraph; solution of digraph; strongly connected digraph; kernels
UR - http://eudml.org/doc/270700
ER -

References

top
  1. [1] M. Behzad and F. Harary, Which directed graphs have a solution?, Math. Slovaca 27 (1977) 37-42. Zbl0368.05027
  2. [2] V.V. Belov, E.M. Vorobjov and V.E. Shatalov, Graph Theory (Vyshshaja Shkola, Moskva, 1976). (Russian) 
  3. [3] C. Berge, Graphs and Hypergraphs (Dunod, Paris, 1970). (French) 
  4. [4] M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). Zbl0411.68039
  5. [5] F. Harary, R.Z. Norman and D. Cartwright, Structural Models (John Wiley & Sons, Inc., New York - London - Sydney, 1965). Zbl0139.41503
  6. [6] M. Harminc, Kernel and solution numbers of digraphs, Acta Univ. M. Belii 6 (1998) 15-20. Zbl0921.05037
  7. [7] M. Harminc and T. Olejnikova, Binary operations on digraphs and solutions, Zb. ved. prac, VST, Košice (1984) 29-42. (Slovak) Zbl0586.05018
  8. [8] L. Lovasz, Combinatorial Problems and Exercises (Akademiai Kiado, Budapest, 1979). 
  9. [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) Zbl0216.02502

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.