Geodesic
(K − 1)-Kernels In Strong K-Transitive Digraphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 229-235

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: digraph, transitive digraph, k-transitive digraph, k-kernel 
@article{DMGT_2015_35_2_a2,
     author = {Wang, Ruixia},
     title = {(K \ensuremath{-} {1)-Kernels} {In} {Strong} {K-Transitive} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {229--235},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a2/}
}
TY  - JOUR
AU  - Wang, Ruixia
TI  - (K − 1)-Kernels In Strong K-Transitive Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 229
EP  - 235
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a2/
LA  - en
ID  - DMGT_2015_35_2_a2
ER  - 
%0 Journal Article
%A Wang, Ruixia
%T (K − 1)-Kernels In Strong K-Transitive Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 229-235
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a2/
%G en
%F DMGT_2015_35_2_a2
Wang, Ruixia. (K − 1)-Kernels In Strong K-Transitive Digraphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 229-235. http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a2/