Kernels in graphs with a clique-cutset (Q1923523): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Henry Jacob / rank | |||
Property / reviewed by | |||
Property / reviewed by: Heinz Joachim Presia / rank | |||
Property / author | |||
Property / author: Henry Jacob / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Heinz Joachim Presia / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4099676 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A remark on a problem of Harary / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Kernels in perfect line-graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 14:43, 24 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Kernels in graphs with a clique-cutset |
scientific article |
Statements
Kernels in graphs with a clique-cutset (English)
0 references
7 October 1996
0 references
Let \(G\) be a finite directed graph without multiple arcs or loops. A kernel of \(G\) is a subset \(K\) of vertices with the following properties: (1) every vertex of \(G - K\) has a successor in \(K\), and (2) there is no arc between any two vertices of \(K\). Not every \(G\) admits a kernel, but many conditions are known that imply the existence of a kernel. \(G\) is called kernel-perfect if every induced subgraph has a kernel. To investigate what kind of graph constructions preserve kernel-perfectness, the concept of clique-cutset is introduced. A clique-cutset \(C\) is a subset of vertices such that \(C\) is a clique and \(G - C\) is disconnected. For every connected component \(A\) of \(G - C\), the subgraph induced by \(A \cup C\) is called a piece of \(G\) with respect to \(C\). The author obtains the following result: Let \(G\) be a directed graph which admits a clique-cutset \(C\). Then \(G\) is kernel-perfect iff every piece of \(G\) with respect to \(C\) is kernel-perfect (Theorem 1).
0 references
kernel-perfect
0 references
clique-cutset
0 references
piece
0 references
directed graph
0 references
0 references