Repositorio Atenea de la Facultad de Ciencias, UNAM >
Repositorio Ciencias >
FACULTAD DE CIENCIAS >
Ciencias >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11154/1642
|
Title: | Kernels in pretransitive digraphs |
Authors: | Rojas-Monroy, R Galeana-Sánchez, H |
Issue Date: | 2004 |
Abstract: | Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A kernel N of D is an independent set of vertices such that for every w is an element of V(D) - N there exists an are from w to N. A digraph D is called right-pretransitive (resp. left-pretransitive) when (u, v) is an element of A(D) and (v, w) is an element of A(D) implies (u, w) is an element of A(D) or (w, v) is an element of A(D) (resp. (u, v) is an element of A(D) and (v, w) is an element of A(D) implies (u, w) is an element of A(D) or (v, u) is an element of A(D)). This concepts were introduced by P. Duchet in 1980. In this paper is proved the following result: Let D be a digraph. If D = D-1 boolean OR D-2 where D-1 is a right-pretransitive digraph, D-2 is a left-pretransitive digraph and D-i contains no infinite outward path for i is an element of {1, 2}, then D has a kernel. (C) 2003 Elsevier B.V. All rights reserved. |
URI: | http://hdl.handle.net/11154/1642 |
ISSN: | 0012-365X |
Appears in Collections: | Ciencias
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|