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


Kernels of digraphs with finitely many ends
Authors:Michał Walicki
Abstract:
According to Richardson’s theorem, every digraph G without directed odd cycles that is either (a) locally finite or (b) rayless has a kernel (an independent subset K with an incoming edge from every vertex in G?K). We generalize this theorem showing that a digraph without directed odd cycles has a kernel when (a) for each vertex, there is a finite set separating it from all rays, or (b) each ray contains at most finitely many vertices dominating it (having an infinite fan to the ray) and the digraph has finitely many ends. The restriction to finitely many ends in (b) can be weakened, admitting infinitely many ends with a specific structure, but the possibility of dropping it remains a conjecture.
Keywords:Digraph kernel  Infinite digraph  End of a digraph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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