DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Semikernels modulo F in Digraphs

Hortensia Galeana-Sánchez, Mucuy-Kak Guevara

Abstract


A kernel N of a digraph D is an independent set of vertices of D such that for every w∈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∈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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional