- Tytuł:
- k-kernels in generalizations of transitive digraphs
- Autorzy:
-
Galeana-Sánchez, Hortensia
Hernández-Cruz, César - Powiązania:
- https://bibliotekanauki.pl/articles/743887.pdf
- Data publikacji:
- 2011
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
digraph
kernel
(k,l)-kernel
k-kernel
transitive digraph
quasi-transitive digraph
right-pretransitive digraph
left-pretransitive digraph
pretransitive digraph - Opis:
-
Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.
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. - Źródło:
-
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 293-312
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł