×

\(H\)-kernels in unions of \(H\)-colored quasi-transitive digraphs. (English) Zbl 1458.05088

Summary: Let \(H\) be a digraph (possibly with loops) and \(D\) a digraph without loops whose arcs are colored with the vertices of \(H (D\) is said to be an \(H\)-colored digraph). For an arc \((x, y)\) of \(D\), its color is denoted by \(c(x, y)\). A directed path \(W = (v_0, \dots, v_n)\) in an \(H\)-colored digraph \(D\) will be called \(H\)-path if and only if \((c(v_0, v_1), \dots, c(v_{n-1}, v_n))\) is a directed walk in \(H\). In \(W\), we will say that there is an obstruction on \(v_i\) if \((c(v_{i-1}, v_i), c(v_i, v_{i+1})) \not\in A(H)\) (if \(v_0 = v_n\) we will take indices modulo \(n\)). A subset \(N\) of \(V (D)\) is said to be an \(H\)-kernel in \(D\) if for every pair of different vertices in \(N\) there is no \(H\)-path between them, and for every vertex \(u\) in \(V (D)\setminus N\) there exists an \(H\)-path in \(D\) from \(u\) to \(N\). Let \(D\) be an arc-colored digraph. The color-class digraph of \(D\), \(\mathcal{C}_C (D)\), is the digraph such that \(V (\mathcal{C}_C (D)) = \{c(a) : a \in A(D)\}\) and \((i, j) \in A(\mathcal{C}_C (D))\) if and only if there exist two arcs, namely \((u, v)\) and \((v, w)\) in \(D\), such that \(c(u, v) = i\) and \(c(v, w) = j\). The main result establishes that if \(D = D_1 \cup D_2\) is an \(H\)-colored digraph which is a union of asymmetric quasi-transitive digraphs and \(\{V_1 ,\dots, V_k\}\) is a partition of \(V (\mathcal{C}_C (D))\) with a property \(P^\ast\) such that

1.) \(V_i\) is a quasi-transitive \(V_i\)-class for every \(i\) in \(\{1,\dots, k\}\),
2.) either \(D[\{a \in A(D) : c(a) \in V_i \}]\) is a subdigraph of \(D_1\) or it is a sudigraph of \(D_2\) for every \(i\) in \(\{1, \dots, k\}\),
3.) \(D_i\) has no infinite outward path for every \(i\) in \(\{1, 2\}\),
4.) every cycle of length three in \(D\) has at most two obstructions, then \(D\) has an \(H\)-kernel.
Some results with respect to the existence of kernels by monochromatic paths in finite digraphs will be deduced from the main result.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Arpin and V. Linek, Reachability problems in edge-colored digraphs, Discrete Math. 307 (2007) 2276-2289. doi:10.1016/j.disc.2006.09.042
[2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2009). doi:10.1007/978-1-84800-998-1 · Zbl 1170.05002
[3] Y. Bai, S. Fujita and S. Zhang, Kernels by properly colored paths in arc-colored digraphs, Discrete Math. 341 (2018) 1523-1533. doi:10.1016/j.disc.2018.02.014 · Zbl 1384.05082
[4] C. Berge, Graphs (North-Holland, Amsterdan, 1989).
[5] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31. doi:10.1016/0012-365X(90)90346-J · Zbl 0721.05027
[6] P. Delgado-Escalante and H. Galeana-Sánchez, Restricted domination in arc-colored digraphs, AKCE Int. J. Graphs Comb. 11 (2014) 95-104.
[7] P. Delgado-Escalante, H. Galeana-Sánchez and E. O’Reilly-Regueiro, Alternating kernels, Discrete Appl. Math. 236 (2018) 153-164. doi:10.1016/j.dam.2017.10.013 · Zbl 1377.05075
[8] H. Galeana-Sánchez, Kernels by monochromatic paths and the color-class digraph, Discuss. Math. Graph Theory 31 (2011) 273-281. doi:10.7151/dmgt.1544 · Zbl 1234.05111
[9] H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103-112. doi:10.1016/0012-365X(95)00036-V · Zbl 0857.05054
[10] H. Galeana-Sánchez and R. Rojas-Monroy, Kernels in quasi-transitive digraphs, Discrete Math. 306 (2006) 1969-1974. doi:10.1016/j.disc.2006.02.015 · Zbl 1100.05042
[11] H. Galeana-Sánchez, B. Llano and J.J. Montellano-Ballesteros, Kernels by monochromatic paths in m-colored unions of quasi-transitive digraphs, Discrete Appl. Math. 158 (2010) 461-466. doi:10.1016/j.dam.2009.11.005 · Zbl 1225.05111
[12] A. Ghouilá-Houri, Caractérisation des graphes non orientés dont on peut orienter les arêtes de manière à obtenir le graphe d’une relation d’ordre, C. R. Math. Acad. Sci. Paris 254 (1962) 1370-1371. · Zbl 0105.35503
[13] V. Linek and B. Sands, A note on paths in edge-colored tournaments, Ars Combin. 44 (1996) 225-228.
[14] K.B. Reid, Monotone reachability in arc-colored tournaments, Congr. Numer. 146 (2000) 131-141. · Zbl 0976.05029
[15] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory Ser. B 33 (1982) 271-275. doi:10.1016/0095-8956(82)90047-8 · Zbl 0488.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.