Kernels in quasi-transitive digraphs |
| |
Authors: | Hortensia Galeana-Sánchez |
| |
Institution: | a Instituto de Matemáticas, UNAM, Ciudad Universitaria, Circuito Exterior, 04510 México D.F., Mexico b Facultad de Ciencias, Universidad Autónoma del Estado de México, Instituto Literario No. 100, Centro 50000, Toluca, Edo. de México, Mexico |
| |
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∈V(D)-N there exists an arc from w to N. A digraph is called quasi-transitive when (u,v)∈A(D) and (v,w)∈A(D) implies (u,w)∈A(D) or (w,u)∈A(D). This concept was introduced by Ghouilá-Houri Caractérisation des graphes non orientés dont on peut orienter les arrêtes de maniere à 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=D1∪D2 where Di is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in Di) for i∈{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. |
| |
Keywords: | Kernel Kernel-perfect digraph Quasi-transitive digraph |
本文献已被 ScienceDirect 等数据库收录! |
|