-kernels in -transitive and -quasi-transitive digraphs

详细信息	查看全文 | 推荐本文 |

• 作者：Cé ; sar Herná ; ndez-Cruz ; ^{cesar@matem.unam.mx} ; ^{japo@ciencias.unam.mx} ; Hortensia Galeana-Sá ; nchez ^{hgaleana@matem.unam.mx}
• 关键词：Digraph ; Kernel ; (k ; l)-kernel ; k-kernel ; Transitive digraph ; Quasi-transitive digraph
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：28 August, 2012
• 卷：312
• 期：16
• 页码：2522-2530
• 文件大小：248 K

摘要

Let be a digraph, and will denote the sets of vertices and arcs of , respectively. A subset of is -independent if for every pair of vertices , we have ; it is -absorbent if for every there exists such that . A -kernel of is a -independent and -absorbent subset of . A -kernel is a -kernel.

A digraph is transitive if for every path in we have . This concept can be generalized as follows, a digraph is quasi-transitive if for every path in , we have or . In the literature, beautiful results describing the structure of both transitive and quasi-transitive digraphs are found that can be used to prove that every transitive digraph has a -kernel for every and that every quasi-transitive digraph has a -kernel for every .

We introduce three new families of digraphs, two of them generalizing transitive and quasi-transitive digraphs respectively; a digraph is -transitive if whenever is a path of length in , then ; -quasi-transitive digraphs are analogously defined, so (quasi-)transitive digraphs are 2-(quasi-)transitive digraphs. We prove some structural results about both classes of digraphs that can be used to prove that a -transitive digraph has an -kernel for every ; that for even , every -quasi-transitive digraph has an -kernel for every ; that every 3-quasi-transitive digraph has -kernel for every . Also, we prove that a -transitive digraph has a -king if and only if it has a unique initial strong component and that a -quasi-transitive digraph has a -king if and only if it has a unique initial strong component.