Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

On independent sets and non-augmentable paths in directed graphs

H. Galeana-Sánchez — 1998

Discussiones Mathematicae Graph Theory

We investigate sufficient conditions, and in case that D be an asymmetrical digraph a necessary and sufficient condition for a digraph to have the following property: "In any induced subdigraph H of D, every maximal independent set meets every non-augmentable path". Also we obtain a necessary and sufficient condition for any orientation of a graph G results a digraph with the above property. The property studied in this paper is an instance of the property of a conjecture of J.M. Laborde, Ch. Payan...

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

H. Galeana-SánchezC. Hernández-Cruz — 2014

Discussiones Mathematicae Graph Theory

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...

KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition

H. Galeana-SánchezV. Neumann-Lara — 1996

Discussiones Mathematicae Graph Theory

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.

Kernels in edge coloured line digraph

H. Galeana-SánchezL. Pastrana Ramírez — 1998

Discussiones Mathematicae Graph Theory

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...

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

H. Galeana-SánchezH.A. Rincón-Mejía — 1998

Discussiones Mathematicae Graph Theory

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...

Page 1

Download Results (CSV)