New extensions of kernel perfect digraphs to kernel imperfect critical digraphs
type: Item
instance of: scholarly article
title: New extensions of kernel perfect digraphs to kernel imperfect critical digraphs
zbMATH Open document ID: 0811.05027
DOI: 10.1007/BF02986683
published in: Graphs and Combinatorics
publication date: 1995-02-01T00:00:00Z
review text: Let \(D\) be a digraph and \(V(D)\) denote its vertex set. If \(K \subseteq V(D)\), then \(N^ -_ D(K)\) denotes the set of vertices in \(V(D) \setminus K\) which dominate at least one vertex of \(K\). A kernel of a digraph \(D\) is a subset \(K \subseteq V(D)\) such that \(K\) is independent (there are no arcs with both end vertices in \(K\)) and \(K \cup N^ -_ D = V(D)\). When every induced subdigraph of \(D\) has a kernel, \(D\) is said to be kernel-perfect. A kernel-perfect digraph \(D\) which does not have a kernel itself is said to be critical kernel-imperfect. The authors present a method to extend a kernel-perfect digraph to a critical kernel- imperfect digraph.
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 716415
zbMATH Keywords: kernel
zbMATH Keywords: digraph
zbMATH Keywords: kernel-perfect digraph
zbMATH Keywords: critical kernel-imperfect digraph
author: Hortensia Galeana-Sánchez
author: V. Neumann-Lara
reviewed by: Brian Alspach
MaRDI profile type: Publication
cites work: Q3680833
cites work: On kernel-perfect critical digraphs
cites work: Extending kernel perfect digraphs to kernel perfect critical digraphs
cites work: KP-digraphs and CKI-digraphs satisfying the \(k\)-Meyniel's condition
cites work: A new method to extend kernel-perfect graphs to kernel-perfect critical graphs
full work available at URL: https://doi.org/10.1007/bf02986683
OpenAlex ID: W1980078505
description: scientific article; zbMATH DE number 716415