Kernels in a special class of digraphs (Q1377857): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4099676 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recent problems and results about kernels in directed graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On kernels in perfect graphs / rank | |||
Normal rank |
Revision as of 10:33, 28 May 2024
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