On a class of kernel-perfect and kernel-perfect-critical graphs (Q685562): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Q5844986 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3941433 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On kernel-perfect critical digraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on kernel-critical graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graphes Noyau-Parfaits / rank
 
Normal rank

Revision as of 09:46, 22 May 2024

scientific article
Language Label Description Also known as
English
On a class of kernel-perfect and kernel-perfect-critical graphs
scientific article

    Statements

    On a class of kernel-perfect and kernel-perfect-critical graphs (English)
    0 references
    0 references
    0 references
    24 February 1994
    0 references
    Let \(G=(V,E)\) be a directed graph. Then a set \(K\) of its vertices is called a kernel if \(K\) is an independent set, and \(K\cap \Gamma^{- 1}(K)=\varnothing\), \(K\cup\Gamma^{-1}(K)=V\), where \(\Gamma^{-1}(K)\) is the set of all the vertices \(x\) of \(G\) such that there exists \(y\in K\) with \((x,y)\) being an arc of \(G\). \(G\) is called a kernel-perfect graph if all induced subgraphs of \(G\), including \(G\), have a kernel, and it is called a kernel-perfect-critical graph if \(G\) does not have a kernel but every proper induced subgraph has. In the paper a new construction of both kernel-perfect graphs and kernel-perfect-critical graphs is presented.
    0 references
    directed graph
    0 references
    kernel
    0 references
    kernel-perfect graph
    0 references
    kernel-perfect-critical graph
    0 references
    0 references

    Identifiers