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/1271
|
Title: | Kernels in quasi-transitive digraphs |
Authors: | Rojas-Monroy, R Galeana-Sánchez, H |
Issue Date: | 2006 |
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 arc from w to N. A digraph is called quasi-transitive when (u, v) is an element of A (D) and (v, w) is an element of A (D) implies (u, v) is an element of A (D) or (w, w) is an element of A (D). This concept was introduced by Ghouila-Houri [Caracterisation des graphes non orientes dont on peut orienter les arretes de maniere a obtenir le graphe d' un relation d'ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371] and has been studied by several authors. In this paper the following result is proved: Let D be a digraph. Suppose D = D-1 boolean OR D-2 where D-i is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in D-i) for i is an element of {1, 2} and that every directed cycle of length 3 contained in D has at least two symmetrical arcs, then D has a kernel. All the conditions for the theorem are tight. (c) 2006 Elsevier B.V. All rights reserved. |
URI: | http://hdl.handle.net/11154/1271 |
ISSN: | 0012-365X |
Appears in Collections: | Ciencias
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|