Kernels in a special class of digraphs (Q1377857)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Kernels in a special class of digraphs |
scientific article |
Statements
Kernels in a special class of digraphs (English)
0 references
2 December 1998
0 references
A digraph \(D\) has a kernel if there is an independent set \(K\) of vertices of \(D\) so that each vertex in \(V(D)-K\) is adjacent to a vertex in \(K\). Further, a digraph \(D\) is complete if for any pair of vertices \(u,v\) at least one of the arcs \((u,v)\) and \((v,u)\) is in \(G\). Let \(D\) be a digraph so that its vertex set can be partitioned in at most three sets with the property that the subgraph induced by any of the sets is complete. The authors give some sufficient conditions for \(D\) to have a kernel.
0 references
kernel
0 references
complete digraph
0 references