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

• Volume: 35, Issue: 2, page 229-235
• ISSN: 2083-5892

top

## Abstract

top
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.

## How to cite

top

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 -

## References

top
1. [1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000). Zbl0958.05002
2. [2] E. Boros and V. Gurvich, Perfect graphs, kernels, and cores of cooperative games, Discrete Math. 306 (2006) 2336-2354. doi:10.1016/j.disc.2005.12.031[Crossref] Zbl1103.05034
3. [3] V. Chvátal, On the computational complexity of finding a kernel, Report No. CRM-300, Centre de Recherches Mathematiques, Universite de Montreal (1973).
4. [4] C. Hernández-Cruz and H. Galeana-Sánchez, k-kernels in k-transitive and k-quasitransitive digraphs, Discrete Math. 312 (2012) 2522-2530. doi:10.1016/j.disc.2012.05.005[Crossref][WoS]
5. [5] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219. doi:10.7151/dmgt.1613[WoS][Crossref]
6. [6] C. Hernández-Cruz, 4-transitive digraphs I: the structure of strong transitive digraphs, Discuss. Math. Graph Theory 33 (2013) 247-260. doi:10.7151/dmgt.1645[WoS][Crossref]
7. [7] C. Hernández-Cruz and J.J. Montellano-Ballesteros, Some remarks on the structure of strong k-transitive digraphs, Discuss. Math. Graph Theory 34 (2014) 651-671. doi:10.7151/dmgt.1765[WoS][Crossref] Zbl1303.05075
8. [8] H. Galeana-Sánchez, C. Hernández-Cruz and M.A. Ju´arez-Camacho, On the existence and number of (k+1)-kings in k-quasi-transitive digraphs, Discrete Math. 313 (2013) 2582-2591. doi:10.1016/j.disc.2013.08.007[Crossref][WoS]
9. [9] M. Kwásnik, On (k, l)-kernels on graphs and their products, Doctoral Dissertation, Technical University of Wroc law, Wroc law, 1980.

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.