(k-1)-KERNELS IN STRONG k-TRANSITIVE DIGRAPHS

作者：Wang Ruixia^*

来源：Discussiones Mathematicae - Graph Theory, 2015, 35(2): 229-235.

DOI：10.7151/dmgt.1787

• digraph
• transitive digraph
• k-transitive digraph
• k-kernel

Let D = (V(D), A (D)) be a digraph and k >= 2 be an integer. A subset N of V (D) is k-independent if for every pair of vertices u, v is an element of N, we have d(u, v) >= k; it is l-absorbent if for every u is an element of V (D) - N, there exists v is an element of N such that d(u, v) <= l. A (k, l)-kernel of D is a k-independent and l-absorbent subset of V(D). A k-kernel is a (k, k - 1)-kernel.
A digraph D is k-transitive if for any path x(0)x(1) ... x(k) of length k, x(0) dominates x(k). Hernandez-Cruz [3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219] proved that a 3-transitive digraph has a 2-kernel if and only if it has no terminal strong component isomorphic to a 3-cycle. In this paper, we generalize the result to strong k-transitive digraphs and prove that a strong k-transitive digraph with k >= 4 has a (k - 1)-kernel if and only if it is not isomorphic to a k-cycle.

• 出版日期2015
• 单位山西大学