ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2018-2019): c. 84%
Discussiones Mathematicae Graph Theory 31(2) (2011)
Instituto de Matemáticas Universidad Nacional Autónoma de México Ciudad Universitaria, México, D.F., C.P. 04510, México
A (k,l)-kernel N of D is a k-independent set of vertices (if
u,v ∈ N, u ≠ v, then d(u,v), d(v,u) ≥ k) and l-absorbent
(if u ∈ V(D)−N then there exists v ∈ N such that d(u,v) ≤ l).
A k-kernel is a (k,k−1)-kernel. Quasi-transitive, right-pretransitive
and left-pretransitive digraphs are generalizations of transitive digraphs.
In this paper the following results are proved: Let D be a right-(left-)
pretransitive strong digraph such that every directed triangle of D is
symmetrical, then D has a k-kernel for every integer k ≥ 3; the result
is also valid for non-strong digraphs in the right-pretransitive case. We also
give a proof of the fact that every quasi-transitive digraph has a
(k,l)-kernel for every integers k > l ≥ 3 or k = 3 and l = 2.
Keywords: digraph, kernel, (k,l)-kernel, k-kernel, transitive digraph, quasi-transitive digraph, right-pretransitive digraph, left-pretransitive digraph, pretransitive digraph
2010 Mathematics Subject Classification: 05C20.
Received 12 November 2009
Revised 23 August 2010
Accepted 24 August 2010