Kernel perfect and critical kernel imperfect digraphs structure

详细信息    查看全文

• 作者：Hortensia Galeana-Sá ; nchez ; Mucuy-kak Guevara
• 关键词：kernel ; semikernel ; semikernel modulo F ; kernel perfect digraph ; critical kernel imperfect digraph
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2007
• 出版时间：1 March 2007
• 年：2007
• 卷：28
• 期：Complete
• 页码：401-408
• 全文大小：210 K

文摘

A kernel N of a digraph D is an independent set of vertices of D such that for every coration:none; color:black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B75GV-4N5M9FJ-21&_mathId=mml1&_user=3986987&_cdi=13104&_rdoc=57&_acct=C000053585&_version=1&_userid=6230853&md5=95ca980e2b045f34a6adf0cad8e0b90a"" title=""Click to view the MathML source"">wc=""http://www.sciencedirect.com/scidirimg/entities/2208.gif"" alt=""set membership, variant"" border=0>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 coration:none; color:black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B75GV-4N5M9FJ-21&_mathId=mml2&_user=3986987&_cdi=13104&_rdoc=57&_acct=C000053585&_version=1&_userid=6230853&md5=58377379ff62340d8a8fd89c52effa40"" title=""Click to view the MathML source"">zc=""http://www.sciencedirect.com/scidirimg/entities/2208.gif"" alt=""set membership, variant"" border=0>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.