Skip to Main content Skip to Navigation
Conference papers

Kernel perfect and critical kernel imperfect digraphs structure

Abstract : 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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184456
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 10:48:10 AM
Last modification on : Thursday, May 11, 2017 - 1:02:53 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:47:16 AM

File

dmAE0151.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184456, version 1

Collections

Citation

Hortensia Galeana-Sánchez, Mucuy-Kak Guevara. Kernel perfect and critical kernel imperfect digraphs structure. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.257-262. ⟨hal-01184456⟩

Share

Metrics

Record views

323

Files downloads

1048