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: 32

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

Wyniki wyszukiwania

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

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

Kernels in the closure of coloured digraphs

100%
Galeana-Sánchez H., García-Ruvalcaba J.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
243-254
EN
Let D be a digraph with V(D) and A(D) the sets of vertices and arcs of D, respectively. A kernel of D is a set I ⊂ V(D) such that no arc of D joins two vertices of I and for each x ∈ V(D)∖I there is a vertex y ∈ I such that (x,y) ∈ A(D). A digraph is kernel-perfect if every non-empty induced subdigraph of D has a kernel. If D is edge coloured, we define the closure ξ(D) of D the multidigraph with V(ξ(D)) = V(D) and $A(ξ(D)) = ⋃_i{(u,v)$ with colour i there exists a monochromatic path of colour i from the vertex u to the vertex v contained in D}. Let T₃ and C₃ denote the transitive tournament of order 3 and the 3-cycle, respectively, both of whose arcs are coloured with 3 different colours. In this paper, we survey sufficient conditions for the existence of kernels in the closure of edge coloured digraphs, also we prove that if D is obtained from an edge coloured tournament by deleting one arc and D does not contain T₃ or C₃, then ξ(D) is a kernel-perfect digraph.
2
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.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect

100%
Galeana-Sánchez H., García-Ruvalcaba J.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
77-93
EN
A digraph D is called a kernel-perfect digraph or KP-digraph when every induced subdigraph of D has a kernel. We call the digraph D an m-coloured digraph if the arcs of D are coloured with m distinct colours. A path P is monochromatic in D if all of its arcs are coloured alike in D. The closure of D, denoted by ζ(D), is the m-coloured digraph defined as follows: V( ζ(D)) = V(D), and A( ζ(D)) = ∪_{i} {(u,v) with colour i: there exists a monochromatic path of colour i from the vertex u to the vertex v contained in D}. We will denoted by T₃ and C₃, the transitive tournament of order 3 and the 3-directed-cycle respectively; both of whose arcs are coloured with three different colours. Let G be a simple graph. By an m-orientation-coloration of G we mean an m-coloured digraph which is an asymmetric orientation of G. By the class E we mean the set of all the simple graphs G that for any m-orientation-coloration D without C₃ or T₃, we have that ζ(D) is a KP-digraph. In this paper we prove that if G is a hamiltonian graph of class E, then its complement has at most one nontrivial component, and this component is K₃ or a star.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On (k,l)-kernels of special superdigraphs of Pₘ and Cₘ

100%
Kucharska M., Kwaśnik M.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
95-109
EN
The concept of (k,l)-kernels of digraphs was introduced in [2]. Next, H. Galeana-Sanchez [4] proved a sufficient condition for a digraph to have a (k,l)-kernel. The result generalizes the well-known theorem of P. Duchet and it is formulated in terms of symmetric pairs of arcs. Our aim is to give necessary and sufficient conditions for digraphs without symmetric pairs of arcs to have a (k,l)-kernel. We restrict our attention to special superdigraphs of digraphs Pₘ and Cₘ.
5
Content available remote

γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs

100%
Casas-Bautista E., Galeana-Sánchez H., Rojas-Monroy R.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
493-507
EN
We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. If D is an m-coloured digraph and a ∈ A(D), colour(a) will denote the colour has been used on a. A path (or a cycle) is called monochromatic if all of its arcs are coloured alike. A γ-cycle in D is a sequence of vertices, say γ = (u0, u1, . . . , un), such that ui ≠ uj if i ≠ j and for every i ∈ {0, 1, . . . , n} there is a uiui+1-monochromatic path in D and there is no ui+1ui-monochromatic path in D (the indices of the vertices will be taken mod n+1). A set N ⊆ V (D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u, v ∈ N there is no monochromatic path between them and; (ii) for every vertex x ∈ V (D) \ N there is a vertex y ∈ N such that there is an xy-monochromatic path. Let D be a finite m-coloured digraph. Suppose that {C1,C2} is a partition of C, the set of colours of D, and Di will be the spanning subdigraph of D such that A(Di) = {a ∈ A(D) | colour(a) ∈ Ci}. In this paper, we give some sufficient conditions for the existence of a kernel by monochromatic paths in a digraph with the structure mentioned above. In particular we obtain an extension of the original result by B. Sands, N. Sauer and R. Woodrow that asserts: Every 2-coloured digraph has a kernel by monochromatic paths. Also, we extend other results obtained before where it is proved that under some conditions an m-coloured digraph has no γ-cycles.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Kernels in edge coloured line digraph

100%
Galeana-Sánchez H., Pastrana Ramírez L.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 1
91-98
EN
We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions (i) for every pair of different vertices u, v ∈ N there is no monochromatic directed path between them and (ii) for every vertex x ∈ V(D)-N there is a vertex y ∈ N such that there is an xy-monochromatic directed path. Let D be an m-coloured digraph and L(D) its line digraph. The inner m-coloration of L(D) is the edge coloration of L(D) defined as follows: If h is an arc of D of colour c, then any arc of the form (x,h) in L(D) also has colour c. In this paper it is proved that if D is an m-coloured digraph without monochromatic directed cycles, then the number of kernels by monochromatic paths in D is equal to the number of kernels by monochromatic paths in the inner edge coloration of L(D).
7
Content available remote

Allocation of oaks to Kraft classes based on linear and nonlinear kernel discriminant variables

100%
Zawieja B., Kaźmierczak K.
Biometrical Letters
|
2016
|
tom 53
|
nr 1
37-46
EN
A method of discriminant variable determination was used to visualize the division of oak trees into Kraft classes. Usual discriminant variables and several types of kernel discriminant variables were studied. For this purpose the traits of oak (Quercus L.) trees, measured on standing trees, were used. These traits included height of tree, breast height diameter and crown projection area. The use of the Gaussian kernel and modified Gaussian kernel enabled the clearest division into Kraft classes. In particular, the latter method proved to be the most effective.
8
Content available remote

γ-Cycles In Arc-Colored Digraphs

100%
Galeana-Sánchez H., Gaytán-Gómez G., Rojas-Monroy R.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
103-116
EN
We call a digraph D an m-colored digraph if the arcs of D are colored with m colors. A directed path (or a directed cycle) is called monochromatic if all of its arcs are colored alike. A subdigraph H in D is called rainbow if all of its arcs have different colors. A set N ⊆ V (D) is said to be a kernel by monochromatic paths of D if it satisfies the two following conditions: for every pair of different vertices u, v ∈ N there is no monochromatic path in D between them, and for every vertex x ∈ V (D) − N there is a vertex y ∈ N such that there is an xy-monochromatic path in D. A γ-cycle in D is a sequence of different vertices γ = (u0, u1, . . . , un, u0) such that for every i ∈ {0, 1, . . . , n}: there is a uiui+1-monochromatic path, and there is no ui+1ui-monochromatic path. The addition over the indices of the vertices of γ is taken modulo (n + 1). If D is an m-colored digraph, then the closure of D, denoted by ℭ(D), is the m-colored multidigraph defined as follows: V (ℭ (D)) = V (D), A(ℭ (D)) = A(D) ∪ {(u, v) with color i | there exists a uv-monochromatic path colored i contained in D}. In this work, we prove the following result. Let D be a finite m-colored digraph which satisfies that there is a partition C = C1 ∪ C2 of the set of colors of D such that: D[Ĉi] (the subdigraph spanned by the arcs with colors in Ci) contains no γ-cycles for i ∈ {1, 2}; If ℭ (D) contains a rainbow C3 = (x0, z, w, x0) involving colors of C1 and C2, then (x0, w) ∈ A(ℭ (D)) or (z, x0) ∈ A(ℭ (D)); If ℭ (D) contains a rainbow P3 = (u, z, w, x0) involving colors of C1 and C2, then at least one of the following pairs of vertices is an arc in ℭ (D): (u, w), (w, u), (x0, u), (u, x0), (x0, w), (z, u), (z, x0). Then D has a kernel by monochromatic paths. This theorem can be applied to all those digraphs that contain no γ-cycles. Generalizations of many previous results are obtained as a direct consequence of this theorem.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Monochromatic paths and quasi-monochromatic cycles in edge-coloured bipartite tournaments

100%
Galeana-Sanchez H., Rojas-Monroy R.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 2
285-306
EN
We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. A directed cycle is called quasi-monochromatic if with at most one exception all of its arcs are coloured alike. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them and (ii) for every vertex x ∈ V(D)∖N there is a vertex y ∈ N such that there is an xy-monochromatic directed path. In this paper it is proved that if D is an m-coloured bipartite tournament such that: every directed cycle of length 4 is quasi-monochromatic, every directed cycle of length 6 is monochromatic, and D has no induced particular 6-element bipartite tournament T̃₆, then D has a kernel by monochromatic paths.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Directed hypergraphs: a tool for researching digraphs and hypergraphs

100%
Galeana-Sánchez H., Manrique M.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
313-335
EN
In this paper we introduce the concept of directed hypergraph. It is a generalisation of the concept of digraph and is closely related with hypergraphs. The basic idea is to take a hypergraph, partition its edges non-trivially (when possible), and give a total order to such partitions. The elements of these partitions are called levels. In order to preserve the structure of the underlying hypergraph, we ask that only vertices which belong to exactly the same edges may be in the same level of any edge they belong to. Some little adjustments are needed to avoid directed walks within a single edge of the underlying hypergraph, and to deal with isolated vertices. The concepts of independent set, absorbent set, and transversal set are inherited directly from digraphs. As a consequence of our results on this topic, we have found both a class of kernel-perfect digraphs with odd cycles and a class of hypergraphs which have a strongly independent transversal set.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Kernels and cycles' subdivisions in arc-colored tournaments

100%
Delgado-Escalante P., Galeana-Sánchez H.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 1
101-117
EN
Let D be a digraph. D is said to be an m-colored digraph if the arcs of D are colored with m colors. A path P in D is called monochromatic if all of its arcs are colored alike. Let D be an m-colored digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following conditions: a) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them; and b) for every vertex x ∈ V(D)-N there is a vertex n ∈ N such that there is an xn-monochromatic directed path in D. In this paper we prove that if T is an arc-colored tournament which does not contain certain subdivisions of cycles then it possesses a kernel by monochromatic paths. These results generalize a well known sufficient condition for the existence of a kernel by monochromatic paths obtained by Shen Minggang in 1988 and another one obtained by Hahn et al. in 2004. Some open problems are proposed.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Monochromatic kernel-perfectness of special classes of digraphs

100%
Galeana-Sánchez H., Ramírez L.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
389-400
EN
In this paper, we introduce the concept of monochromatic kernel-perfect digraph, and we prove the following two results: (1) If D is a digraph without monochromatic directed cycles, then D and each $α_v,v ∈ V(D)$ are monochromatic kernel-perfect digraphs if and only if the composition over D of $(α_v)_{v ∈ V(D)}$ is a monochromatic kernel-perfect digraph. (2) D is a monochromatic kernel-perfect digraph if and only if for any B ⊆ V(D), the duplication of D over B, $D^B$, is a monochromatic kernel-perfect digraph.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Kernels by monochromatic paths and the color-class digraph

100%
Galeana-Sánchez H.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
273-281
EN
An m-colored digraph is a digraph whose arcs are colored with m colors. A directed path is monochromatic when its arcs are colored alike. A set S ⊆ V(D) is a kernel by monochromatic paths whenever the two following conditions hold: 1. For any x,y ∈ S, x ≠ y, there is no monochromatic directed path between them. 2. For each z ∈ (V(D)-S) there exists a zS-monochromatic directed path. In this paper it is introduced the concept of color-class digraph to prove that if D is an m-colored strongly connected finite digraph such that: (i) Every closed directed walk has an even number of color changes, (ii) Every directed walk starting and ending with the same color has an even number of color changes, then D has a kernel by monochromatic paths. This result generalizes a classical result by Sands, Sauer and Woodrow which asserts that any 2-colored digraph has a kernel by monochromatic paths, in case that the digraph D be a strongly connected digraph.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On (k,l)-kernel perfectness of special classes of digraphs

100%
Kucharska M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
103-119
EN
In the first part of this paper we give necessary and sufficient conditions for some special classes of digraphs to have a (k,l)-kernel. One of them is the duplication of a set of vertices in a digraph. This duplication come into being as the generalization of the duplication of a vertex in a graph (see [4]). Another one is the D-join of a digraph D and a sequence α of nonempty pairwise disjoint digraphs. In the second part we prove theorems, which give necessary and sufficient conditions for special digraphs presented in the first part to be (k,l)-kernel-perfect digraphs. The concept of a (k,l)-kernel-perfect digraph is the generalization of the well-know idea of a kernel perfect digraph, which was considered in [1] and [6].
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Monochromatic cycles and monochromatic paths in arc-colored digraphs

100%
Galeana-Sánchez H., Gaytán-Gómez G., Rojas-Monroy R.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
283-292
EN
We call the digraph D an m-colored digraph if the arcs of D are colored with m colors. A path (or a cycle) is called monochromatic if all of its arcs are colored alike. A cycle is called a quasi-monochromatic cycle if with at most one exception all of its arcs are colored alike. A subdigraph H in D is called rainbow if all its arcs have different colors. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v ∈ N there is no monochromatic path between them and; (ii) for every vertex x ∈ V(D)-N there is a vertex y ∈ N such that there is an xy-monochromatic path. The closure of D, denoted by ℭ(D), is the m-colored multidigraph defined as follows: V(ℭ(D)) = V(D), A(ℭ(D)) = A(D)∪{(u,v) with color i | there exists a uv-monochromatic path colored i contained in D}. Notice that for any digraph D, ℭ (ℭ(D)) ≅ ℭ(D) and D has a kernel by monochromatic paths if and only if ℭ(D) has a kernel. Let D be a finite m-colored digraph. Suppose that there is a partition C = C₁ ∪ C₂ of the set of colors of D such that every cycle in the subdigraph $D[C_i]$ spanned by the arcs with colors in $C_i$ is monochromatic. We show that if ℭ(D) does not contain neither rainbow triangles nor rainbow P₃ involving colors of both C₁ and C₂, then D has a kernel by monochromatic paths. This result is a wide extension of the original result by Sands, Sauer and Woodrow that asserts: Every 2-colored digraph has a kernel by monochromatic paths (since in this case there are no rainbow triangles in ℭ(D)).
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On monochromatic paths and bicolored subdigraphs in arc-colored tournaments

100%
Delgado-Escalante P., Galeana-Sánchez H.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
791-820
EN
Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n ∈ N such that there is a monochromatic directed path from v to n. In this paper we prove different sufficient conditions which imply that an arc-colored tournament has a kernel by monochromatic paths. Our conditions concerns to some subdigraphs of T and its quasimonochromatic and bicolor coloration. We also prove that our conditions are not mutually implied and that they are not implied by those known previously. Besides some open problems are proposed.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel

100%
Galeana-Sánchez H.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
171-182
EN
A kernel N of a digraph D is an independent set of vertices of D such that for every w ∈ V(D)-N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel-perfect digraph. In this paper I investigate some sufficient conditions for a digraph to have a kernel by asking for the existence of certain diagonals or symmetrical arcs in each odd directed cycle whose length is at most 2α(D)+1, where α(D) is the maximum cardinality of an independent vertex set of D. Previous results are generalized.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

New classes of critical kernel-imperfect digraphs

88%
Galeana-Sánchez H., Neumann-Lara V.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 1
85-89
EN
A kernel of a digraph D is a subset N ⊆ V(D) which is both independent and absorbing. When every induced subdigraph of D has a kernel, the digraph D is said to be kernel-perfect. We say that D is a critical kernel-imperfect digraph if D does not have a kernel but every proper induced subdigraph of D does have at least one. Although many classes of critical kernel-imperfect-digraphs have been constructed, all of them are digraphs such that the block-cutpoint tree of its asymmetrical part is a path. The aim of the paper is to construct critical kernel-imperfect digraphs of a special structure, a general method is developed which permits to build critical kernel-imperfect-digraphs whose asymmetrical part has a prescribed block-cutpoint tree. Specially, any directed cactus (an asymmetrical digraph all of whose blocks are directed cycles) whose blocks are directed cycles of length at least 5 is the asymmetrical part of some critical kernel-imperfect-digraph.
19
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the lattice of congruences on inverse semirings

88%
Bhuniya A., Bhuniya A.
Discussiones Mathematicae - General Algebra and Applications
|
2008
|
tom 28
|
nr 2
193-208
EN
Let S be a semiring whose additive reduct (S,+) is an inverse semigroup. The relations θ and k, induced by tr and ker (resp.), are congruences on the lattice C(S) of all congruences on S. For ρ ∈ C(S), we have introduced four congruences $ρ_{min}, ρ_{max}, ρ^{min}$ and $ρ^{max}$ on S and showed that $ρθ = [ρ_{min},ρ_{max}]$ and $ρκ = [ρ^{min},ρ^{max}]$. Different properties of ρθ and ρκ have been considered here. A congruence ρ on S is a Clifford congruence if and only if $ρ_{max}$ is a distributive lattice congruence and $ρ^{max}$ is a skew-ring congruence on S. If η (σ) is the least distributive lattice (resp. skew-ring) congruence on S then η ∩ σ is the least Clifford congruence on S.
20
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The Clifford semiring congruences on an additive regular semiring

88%
Bhuniya A.
Discussiones Mathematicae - General Algebra and Applications
|
2014
|
tom 34
|
nr 2
143-153
EN
A congruence ρ on a semiring S is called a (generalized)Clifford semiring congruence if S/ρ is a (generalized)Clifford semiring. Here we characterize the (generalized)Clifford congruences on a semiring whose additive reduct is a regular semigroup. Also we give an explicit description for the least (generalized)Clifford congruence on such semirings.
first rewind previous Strona / 2 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ć.