×

Quasi-kernels and quasi-sinks in infinite graphs. (English) Zbl 1208.05033

Summary: Given a directed graph \(G=(V,E)\) an independent set \(A\subset V\) is called quasi-kernel (quasi-sink) iff for each point \(v\) there is a path of length at most 2 from some point of \(A\) to \(v\) (from \(v\) to some point of \(A\)). Every finite directed graph has a quasi-kernel. The plain generalization for infinite graphs fails, even for tournaments. We study the following conjecture: for any digraph \(G=(V,E)\) there is a partition \((V_{0},V_{1})\) of the vertex set such that the induced subgraph \(G[V_{0}]\) has a quasi-kernel and the induced subgraph \(G[V_{1}]\) has a quasi-sink.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C63 Infinite graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chvátal, V.; Lovász, L., Every directed graph has a semi-kernel, Lecture Notes Math., 411, 175 (1974) · Zbl 0297.05116
[2] Galeana-Sánchez, H.; Li, Xueliang, Semikernels and \((k, l)\)-kernels in digraphs, SIAM J. Discrete Math., 11, 340-346 (1998) · Zbl 0907.05025
[3] Gutin, G.; Koh, K. M.; Tay, E. G.; Yao, A., On the number of quasi-kernels in digraphs, J. Graph Theory, 46, 48-56 (2004) · Zbl 1051.05046
[4] Jacob, H.; Meyniel, H., About quasi-kernels in a digraph, Discrete Math., 154, 279-280 (1996) · Zbl 0854.05055
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.