On the existence of 3- and 4-kernels in digraphs |
| |
Authors: | Sebastián González Hermosillo de la Maza César Hernández-Cruz |
| |
Institution: | Facultad de Ciencias, UNAM, Av. Universidad 3000, Circuito Exterior S/N, Delegación Coyoacán, C.P. 04510 Ciudad Universitaria, D.F., Mexico |
| |
Abstract: | Let be a digraph. A subset is -independent if the distance between every pair of vertices of is at least , and it is -absorbent if for every vertex in there exists such that the distance from to is less than or equal to . A -kernel is a -independent and -absorbent set. A kernel is simply a -kernel.A classical result due to Duchet states that if every directed cycle in a digraph has at least one symmetric arc, then has a kernel. We propose a conjecture generalizing this result for -kernels and prove it true for and . |
| |
Keywords: | Kernel Kernel-perfect digraph Corresponding author |
本文献已被 ScienceDirect 等数据库收录! |
|