Kernels in Orientations of Pretransitive Orientable Graphs
Hortensia Galeana‐Sánchez, Rocı́o Rojas-Monroy · Birkhäuser Basel eBooks · 2006
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 D is called right-pretransitive (resp. left-pretransitive) when (u,v) ∈ A(D) and (v,w) ∈ A(D) implies (u,w) ∈ A(D) or (w,v) ∈ A(D) (resp. (u,v) ∈ A(D) and (v,w) ∈ A(D) implies (u,w) ∈ A(D) or (v,u) ∈ A(D)). These concepts were introduced by P. Duchet in 1980. Let G be a graph, an orientation of G is a digraph obtained from G by directing each edge of G in at least one of the two possible directions; an orientation D of G is: a right (resp. left)-pretrantive orientation of G if D is a right (resp. left)-pretransitive digraph; and D is a Meyniel-orientation or M-orientation of G, if every directed cycle of length 3 of D has at least two symmetrical arcs. In this paper the following result is proved: Let G be a simple (possible infinite) graph, and D an Morientation of G. If there exists a right (resp. left)-pretransitive orientation T of G such that T has no infinite outward path nor infinite inward path either, and Sym(T) = Sym(D), then D has a kernel. Previous results are generalized.