Hortensia Galeana-Sánchez ; Mucuy-Kak Guevara - Kernel perfect and critical kernel imperfect digraphs structure

dmtcs:3467 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3467
Kernel perfect and critical kernel imperfect digraphs structureArticle

Authors: Hortensia Galeana-Sánchez 1; Mucuy-Kak Guevara 1

  • 1 Instituto de Matematicas

A kernel $N$ of a digraph $D$ is an independent set of vertices of $D$ such that for every $w \in V(D)-N$ there exists an arc from $w$ to $N$. If every induced subdigraph of $D$ has a kernel, $D$ is said to be a kernel perfect digraph. Minimal non-kernel perfect digraph are called critical kernel imperfect digraph. If $F$ is a set of arcs of $D$, a semikernel modulo $F$, $S$ of $D$ is an independent set of vertices of $D$ such that for every $z \in V(D)- S$ for which there exists an $Sz-$arc of $D-F$, there also exists an $zS-$arc in $D$. In this talk some structural results concerning critical kernel imperfect and sufficient conditions for a digraph to be a critical kernel imperfect digraph are presented.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: critical kernel imperfect digraph,kernel,semikernel,semikernel modulo F,kernel perfect digraph,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

Consultation statistics

This page has been seen 200 times.
This article's PDF has been downloaded 345 times.