首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 D=(V(D),A(D)) be a digraph. A subset S?V(D) is k-independent if the distance between every pair of vertices of S is at least k, and it is ?-absorbent if for every vertex u in V(D)?S there exists vS such that the distance from u to v is less than or equal to ?. A k-kernel is a k-independent and (k?1)-absorbent set. A kernel is simply a 2-kernel.A classical result due to Duchet states that if every directed cycle in a digraph D has at least one symmetric arc, then D has a kernel. We propose a conjecture generalizing this result for k-kernels and prove it true for k=3 and k=4.
Keywords:Kernel  Kernel-perfect digraph  Corresponding author  
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号