×

zbMATH — the first resource for mathematics

On kernel-perfect critical digraphs. (English) Zbl 0593.05034
Let G be a digraph. An independent set N of vertices of G is called a kernel if for every vertex z of G, \(z\not\in N\), there exists a vertex \(v\in N\) such that (z,v) is an edge of G. A digraph is said to be kernel- perfect (KP) if each of its proper induced subdigraphs has a kernel. A KP digraph which has no kernel is called KP-critical. In the paper some properties of KP-critical digraphs are studied and a construction of such digraphs is given. In a addition, the sufficient conditions for a digraph to be KP are investigated.
Reviewer: P.Horák

MSC:
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[2] Duchet, P., Representation; noyaux en theorie des graphes et hypergraphes, (), Paris
[3] Duchet, P., Graphes noyau-parfaits, Ann. discrete math., 9, 93-101, (1980) · Zbl 0462.05033
[4] Duchet, P.; Meyniel, H., A note on kernel-critical graphs, Discrete math., 33, 103-105, (1981) · Zbl 0456.05032
[5] Erdös, P., Problems and results in number theory and graph theory, (), 3-21
[6] Galeana-Sánchez, H., A counterexample to a conjecture of meyniel on kernel-perfect graphs, Discrete math., 41, 105-107, (1982) · Zbl 0484.05035
[7] Galeana-Sánchez, H.; Neumann-Lara, V., On kernels and semikernels of digraphs, Discrete math., 48, 67-76, (1984) · Zbl 0529.05024
[8] H. Galeana-Sánchez and V. Neumann-Lara, Extending kernel-perfect digraphs to kernel-perfect critical digraphs, preprint. · Zbl 0748.05060
[9] Harary, F.; Norman, R.Z.; Cartwright, D., Structural models, (1965), Wiley New York · Zbl 0139.41503
[10] Jacob, H., Etude theórique du noyau d’un graphe, ()
[11] H. Meyniel, Extension du nombre chromatique et du nombre de stabilité, preprint.
[12] Neumann-Lara, V., Seminúcleos de una digráfica, An. inst. mat. univ. nac. autónoma México II, (1971)
[13] Neumann-Lara, V., The dichromatic number of a digraph, J. combin. theory ser. B, 33, 3, 265-270, (1982) · Zbl 0506.05031
[14] Richardson, M., On weakly ordered systems, Bull. amer. math. soc., 52, 113, (1946) · Zbl 0060.06506
[15] Richardson, M., Solutions of irreflexive relations, Ann. math., 58, 2, 573, (1953) · Zbl 0053.02902
[16] Richardson, M., Extension theorems for solutions of irreflexive relations, (), 649 · Zbl 0053.02903
[17] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton Univ. Press, Princeton). · Zbl 0063.05930
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.