(K − 1)-Kernels In Strong K-Transitive Digraphs

Ruixia Wang. "(K − 1)-Kernels In Strong K-Transitive Digraphs." Discussiones Mathematicae Graph Theory 35.2 (2015): 229-235. <http://eudml.org/doc/271099>.

@article{RuixiaWang2015,
abstract = {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 ∈ N, we have d(u, v) ≥ k; it is l-absorbent if for every u ∈ V (D) − N, there exists v ∈ 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 x0x1 ・ ・ ・ xk of length k, x0 dominates xk. Hernández-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.},
author = {Ruixia Wang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {digraph; transitive digraph; k-transitive digraph; k-kernel; -transitive digraph; -kernel},
language = {eng},
number = {2},
pages = {229-235},
title = {(K − 1)-Kernels In Strong K-Transitive Digraphs},
url = {http://eudml.org/doc/271099},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Ruixia Wang
TI - (K − 1)-Kernels In Strong K-Transitive Digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 229
EP - 235
AB - 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 ∈ N, we have d(u, v) ≥ k; it is l-absorbent if for every u ∈ V (D) − N, there exists v ∈ 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 x0x1 ・ ・ ・ xk of length k, x0 dominates xk. Hernández-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.
LA - eng
KW - digraph; transitive digraph; k-transitive digraph; k-kernel; -transitive digraph; -kernel
UR - http://eudml.org/doc/271099
ER -