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

Discussiones Mathematicae Graph Theory (2015)

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

## Access Full Article

top## Abstract

top## How to cite

topRuixia 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] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000). Zbl0958.05002
- [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] V. Chvátal, On the computational complexity of finding a kernel, Report No. CRM-300, Centre de Recherches Mathematiques, Universite de Montreal (1973).
- [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] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219. doi:10.7151/dmgt.1613[WoS][Crossref]
- [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] 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] 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] M. Kwásnik, On (k, l)-kernels on graphs and their products, Doctoral Dissertation, Technical University of Wroc law, Wroc law, 1980.

## NotesEmbed ?

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