Semikernels modulo \(F\) and kernels in digraphs (Q1978146)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Semikernels modulo \(F\) and kernels in digraphs
scientific article

    Statements

    Semikernels modulo \(F\) and kernels in digraphs (English)
    0 references
    24 July 2000
    0 references
    Let \(D=(V,A)\) be a finite digraph and let \(V\) and \(A\) denote the set of all vertices and arcs of \(D,\) respectively. A set \(S\) of vertices is defined to be a semikernel of \(D\) modulo \(F\) if \(S\subseteq V,\) \(F\subseteq A,\) \(S\) is independent in \(D\) and for every \(z\in V-S\) for which there is an \(Sz\)-arc belonging to \(D-F,\) there exists a \(zS\)-arc in \(A.\) A new sufficient condition for a digraph to have a kernel is obtained and a result of \textit{B. Sands, N. Sauer} and \textit{R. Woodrow} on monochromatic paths [J. Comb. Theory, Ser. B 33, 271-275 (1982; Zbl 0488.05036)] is generalized.
    0 references
    kernel
    0 references
    semikernel
    0 references
    semikernel modulo \(F\)
    0 references

    Identifiers