On the dichromatic number in kernel theory
Hortensia Galeana-Sánchez, V. Neumann-Lara (1998)
Mathematica Slovaca
Similarity:
Displaying similar documents to “Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel”
On the dichromatic number in kernel theory
KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition
H. Galeana-Sánchez, V. Neumann-Lara (1996)
Discussiones Mathematicae Graph Theory
Similarity:
A digraph D is said to satisfy the k-Meyniel's condition if each odd directed cycle of D has at least k diagonals. The study of the k-Meyniel's condition has been a source of many interesting problems, questions and results in the development of Kernel Theory. In this paper we present a method to construct a large variety of kernel-perfect (resp. critical kernel-imperfect) digraphs which satisfy the k-Meyniel's condition.
On (k,l)-kernel perfectness of special classes of digraphs
Magdalena Kucharska (2005)
Discussiones Mathematicae Graph Theory
Similarity:
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...
On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect
Hortensia Galeana-Sánchez, José de Jesús García-Ruvalcaba (2001)
Discussiones Mathematicae Graph Theory
Similarity:
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...
Kernels by Monochromatic Paths and Color-Perfect Digraphs
Hortensia Galeana-Śanchez, Rocío Sánchez-López (2016)
Discussiones Mathematicae Graph Theory
Similarity:
For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different...
A sufficient condition for the existence of k-kernels in digraphs
H. Galeana-Sánchez, H.A. Rincón-Mejía (1998)
Discussiones Mathematicae Graph Theory
Similarity:
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...
On (k,l)-kernels in D-join of digraphs
Waldemar Szumny, Andrzej Włoch, Iwona Włoch (2007)
Discussiones Mathematicae Graph Theory
Similarity:
In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.
On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
Pavol Hell, César Hernández-Cruz (2014)
Discussiones Mathematicae Graph Theory
Similarity:
Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) 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 (D) − 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 (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in...
Which directed graphs have a solution?
Mehdi Behzad, Frank Harary (1977)
Mathematica Slovaca
Similarity:
On the Existence of (k,l)-Kernels in Infinite Digraphs: A Survey
H. Galeana-Sánchez, C. Hernández-Cruz (2014)
Discussiones Mathematicae Graph Theory
Similarity:
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...
k-Kernels and some operations in digraphs
Hortensia Galeana-Sanchez, Laura Pastrana (2009)
Discussiones Mathematicae Graph Theory
Similarity:
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...
New classes of critical kernel-imperfect digraphs
Hortensia Galeana-Sánchez, V. Neumann-Lara (1998)
Discussiones Mathematicae Graph Theory
Similarity:
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...
On (k,l)-kernels of special superdigraphs of Pₘ and Cₘ
Magdalena Kucharska, Maria Kwaśnik (2001)
Discussiones Mathematicae Graph Theory
Similarity:
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ₘ.
Kernels in the closure of coloured digraphs
Hortensia Galeana-Sánchez, José de Jesús García-Ruvalcaba (2000)
Discussiones Mathematicae Graph Theory
Similarity:
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 Let T₃ and C₃ denote the transitive tournament of order 3 and the 3-cycle,...
A note on kernels and solutions in digraphs
Matúš Harminc, Roman Soták (1999)
Discussiones Mathematicae Graph Theory
Similarity:
For given nonnegative integers k,s an upper bound on the minimum number of vertices of a strongly connected digraph with exactly k kernels and s solutions is presented.
k-kernels in generalizations of transitive digraphs
Hortensia Galeana-Sánchez, César Hernández-Cruz (2011)
Discussiones Mathematicae Graph Theory
Similarity:
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:...