On \((k,l)\)-kernels of special superdigraphs of \(P_m\) and \(C_m\)
A digraph \(D=(V,A)\) is a finite, asymmetrically directed graph without loops and multiple arcs. A subset \(K\) of \(V\) is called a \((k,l)\)-kernel of \(D\) if \(K\) is \(k\)-stable and \(l\)-dominating in \(D\). Let \(C_m\) (\(P_m\)) denote a circuit (directed path) with \(m\) vertices. Necessary and sufficient conditions for \(C_m\) (\(P_m\)) to have a \((k,l)\)-kernel are found. The authors estimate a number of additional arcs needed for creating a spanning superdigraph of \(C_m\) (\(P_m\)) that possesses a \((k,l)\)-kernel. If a \((k,l)\)-kernel \(K\) of \(D\) is neither \((k+1)\)-stable nor \((l-1)\)-dominating in \(D\) then \(K\) is said to be a strong \((k,l)\)-kernel of \(D\). A reduction of the existence of a strong \((k,l)\)-kernel in \(C_m\) to the existence of a \((k,l)\)-kernel in \(C_{m-k-l-1}\) is described.
scientific article; zbMATH DE number 1709172