Richardson's Theorem for k-colored kernels in strongly connected digraphs
Por:
Galeana-Sanchez, Hortensia, Jose Montellano-Ballesteros, Juan
Publicada:
20 abr 2016
Resumen:
A digraph D=(V,A) is said to be m-colored if its arcs are colored with m colors. An m-colored digraph D has a k-colored kernel if there exists K?V such that (i) for every veV\K there exist a q-colored directed path, with q=k, from v to a vertex of K, and (ii) for every pair {u,v}?K every directed path from u to v uses at least k+1 colors. Given an m-colored digraph D, the color-class digraph of D, denoted C(D), is defined as follows: the vertices of C(D) are the m colors of D, and (i,j) is an arc of C(D) if and only if there exist two consecutive arcs in D, namely (u,v) and (v,w), such that (u,v) has color i and (v,w) has color j. A digraph D is said to be cyclically k-partite if there is a partition {Vi}i=0k-1 of its vertices in independent sets such that every arc in D is either a loop or a ViVi+1-arc (taken the index modulo k). In Galeana-Sánchez (2012) it was proved that given an m-colored digraph D, if C(D) is cyclically 2-partite then D has a kernel by monochromatic paths (that is a 1-colored kernel). In this paper we extend this work and prove the following: Let D be a strongly connected m-colored digraph D such that, for some k=1, C(D) is a cyclically (k+1)-partite digraph, with partition {Ci}i=0k. (i) If for some part Cj, no vertex of Cj has a loop, then D has a k-colored kernel. (ii) For each i, with 0=i=k, let Di be the subgraph of D induced by the set of arcs with color in Ci, and for each vertex x of D let NC+(x) and NC-(x) be the set of colors appearing in the ex-arcs and in-arcs of x, respectively. If for some subdigraph Dj, for every vertex x of Dj we have that NC+(x)?NC-(x), then D has a k-colored kernel. As a direct consequence we obtain a proof of Richardson's Theorem in the case D is strongly connected, and a proof of a classical result by M. Kwas¨nik (see Kwas¨nik (1983)) on the existence of k-kernels (a k-kernel of a digraph D=(V,A) is a set S?V such that for any veV\S, dD(v,S)=k-1 and for every pair {u,v}?S, dD(u,v)=k) that asserts that if D is a strongly connected digraph such that every directed cycle has length congruent with 0 modulo k, then D has a k-kernel. © 2016 Elsevier B.V. All rights reserved. All rights reserved.
Filiaciones:
Galeana-Sanchez, Hortensia:
Univ Nacl Autonoma Mexico, Inst Matemat, Ciudad Univ, Mexico City 04510, DF, Mexico
Jose Montellano-Ballesteros, Juan:
Univ Nacl Autonoma Mexico, Inst Matemat, Ciudad Univ, Mexico City 04510, DF, Mexico
|