Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 7

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  k-kernel
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A sufficient condition for the existence of k-kernels in digraphs

100%
Galeana-Sánchez H., Rincón-Mejía H.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 2
197-204
EN
In this paper, we prove the following sufficient condition for the existence of k-kernels in digraphs: Let D be a digraph whose asymmetrical part is strongly conneted and such that every directed triangle has at least two symmetrical arcs. If every directed cycle γ of D with l(γ) ≢ 0 (mod k), k ≥ 2 satisfies at least one of the following properties: (a) γ has two symmetrical arcs, (b) γ has four short chords. Then D has a k-kernel. This result generalizes some previous results on the existence of kernels and k-kernels in digraphs. In particular, it generalizes the following Theorem of M. Kwaśnik [5]: Let D be a strongly connected digraph, if every directed cycle of D has length ≡ 0 (mod k), k ≥ 2. Then D has a k-kernel.
2
Content available remote

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

100%
Wang R.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
229-235
EN
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.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

k-Kernels and some operations in digraphs

100%
Galeana-Sanchez H., Pastrana L.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 1
39-49
EN
Let D be a digraph. V(D) denotes the set of vertices of D; a set N ⊆ V(D) is said to be a k-kernel of D if it satisfies the following two conditions: for every pair of different vertices u,v ∈ N it holds that every directed path between them has length at least k and for every vertex x ∈ V(D)-N there is a vertex y ∈ N such that there is an xy-directed path of length at most k-1. In this paper, we consider some operations on digraphs and prove the existence of k-kernels in digraphs formed by these operations from another digraphs.
4
Content available remote

On the Existence of (k,l)-Kernels in Infinite Digraphs: A Survey

88%
Galeana-Sánchez H., Hernández-Cruz C.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
431-466
EN
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 (if u, v ∈ N, u 6= 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) set of vertices. A k-kernel is a (k, k −1)-kernel. This work is a survey of results proving sufficient conditions for the existence of (k, l)-kernels in infinite digraphs. Despite all the previous work in this direction was done for (2, 1)-kernels, we present many original results concerning (k, l)-kernels for distinct values of k and l. The original results are sufficient conditions for the existence of (k, l)- kernels in diverse families of infinite digraphs. Among the families that we study are: transitive digraphs, quasi-transitive digraphs, right/left pretransitive digraphs, cyclically k-partite digraphs, κ-strong digraphs, k-transitive digraphs, k-quasi-transitive digraphs
5
Content available remote

Some Results on 4-Transitive Digraphs

88%
García-Vázquez P. R., Hernández-Cruz C.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
117-129
EN
Let D be a digraph with set of vertices V and set of arcs A. We say that D is k-transitive if for every pair of vertices u, v ∈ V, the existence of a uv-path of length k in D implies that (u, v) ∈ A. A 2-transitive digraph is a transitive digraph in the usual sense. A subset N of V is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V \ N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V. The problem of determining whether a digraph has a k-kernel is known to be 𝒩𝒫-complete for every k ≥ 2. In this work, we characterize 4-transitive digraphs having a 3-kernel and also 4-transitive digraphs having a 2-kernel. Using the latter result, a proof of the Laborde-Payan-Xuong conjecture for 4-transitive digraphs is given. This conjecture establishes that for every digraph D, an independent set can be found such that it intersects every longest path in D. Also, Seymour’s Second Neighborhood Conjecture is verified for 4-transitive digraphs and further problems are proposed.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Cyclically k-partite digraphs and k-kernels

88%
Galeana-Sánchez H., Hernández-Cruz C.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
63-78
EN
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 then d(u,v) ≥ 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. A digraph D is cyclically k-partite if there exists a partition ${V_i}_{i = 0}^{k-1}$ of V(D) such that every arc in D is a $V_i V_{i+1}-arc$ (mod k). We give a characterization for an unilateral digraph to be cyclically k-partite through the lengths of directed cycles and directed cycles with one obstruction, in addition we prove that such digraphs always have a k-kernel. A study of some structural properties of cyclically k-partite digraphs is made which bring interesting consequences, e.g., sufficient conditions for a digraph to have k-kernel; a generalization of the well known and important theorem that states if every cycle of a graph G has even length, then G is bipartite (cyclically 2-partite), we prove that if every cycle of a graph G has length ≡ 0 (mod k) then G is cyclically k-partite; and a generalization of another well known result about bipartite digraphs, a strong digraph D is bipartite if and only if every directed cycle has even length, we prove that an unilateral digraph D is bipartite if and only if every directed cycle with at most one obstruction has even length.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

k-kernels in generalizations of transitive digraphs

63%
Galeana-Sánchez H., Hernández-Cruz C.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
293-312
EN
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.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.