×

\(H\)-kernels by walks in subdivision digraph. (English) Zbl 1463.05221

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). A directed walk \(W\) in \(D\) is said to be an \(H\)-walk if and only if the consecutive colors encountered on \(W\) form a directed walk in \(H\). A subset \(N\) of the vertices of \(D\) is said to be an \(H\)-kernel by walks if (1) for every pair of different vertices in \(N\) there is no \(H\)-walk between them \((N\) is \(H\)-independent by walks) and (2) for each vertex \(u\) in \(V(D)-N\) there exists an \(H\)-walk from \(u\) to \(N\) in \(D (N\) is \(H\)-absorbent by walks). Suppose that \(D\) is a digraph possibly infinite. In this paper we will work with the subdivision digraph \(S_H(D)\) of \(D\), where \(S_H(D)\) is an \(H\)-colored digraph defined as follows: \(V(S_H(D)) = V(D) \cup A(D)\) and \(A(S_H(D))\) = {\((u,a) :(a = (u,v)\in A(D)\} \cup \{(a,v) : a = (u,v) \in A(D)\}\), where \((u, a, v)\) is an \(H\)-walk in \(S_H(D)\) for every \(a = (u,v)\) in \(A(D)\). We will show sufficient conditions on \(D\) and on \(S_H(D)\) which guarantee the existence or uniqueness of \(H\)-kernels by walks in \(S_H(D)\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Arpin and V. Linek, Reachability problems in edge-colored digraphs,Discrete Math.,307(2007) 2276-2289.
[2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, London, 2000. · Zbl 1001.05002
[3] C. Berge,Graphs, North-Holland, Amsterdan, 1989.
[4] E. Boros, V. Gurvich, Perfect graphs, kernels and cores of cooperative games, RUTCOR Research Report 12. Rutgers University, april 2003. · Zbl 1103.05034
[5] V. Chv´atal, On the computational complexity of finding a kernel, Report CRM300, Centre de Recherches Math´ematiques, Universit´e de Montr´eal, 1973.
[6] A. S. Fraenkel, Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction,Electron J. Combin.,14(DS2) (2009). · Zbl 1062.91016
[7] H. Galeana-S´anchez and R. Rojas-Monroy, Kernels and some operations in edge-coloured digraphs,Discrete Math., 308(2008) 6036-6046. · Zbl 1160.05025
[8] T. W. Haynes, S.T. Hedetniemi and P. J. Slater, Domination in graphs: advanced topics. Monographs and textbooks in pure and applied mathematics 209, Marcel Dekker Inc, New York , 1998.
[9] T. W. Haynes, S.T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Chapman and Hall/CRC Pure and Applied Mathematics 464. Marcel Dekker Inc, New York, 1998. · Zbl 0890.05002
[10] V. Linek and B. Sands, A note on paths in edge-colored tournaments,Ars Combin.,44(1996) 225-228.
[11] von J. Neumann and O. Morgenstern, Theory of games and economic behavior, Princeton University Press, Princeton, NJ, 1944. · Zbl 0063.05930
[12] R. Rojas-Monroy and J. I. Villarreal-Vald´es, Kernels in infinite digraphs,AKCE J. Graphs. Combin.,7no. 1 (2010) 103-111. · Zbl 1223.05101
[13] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge coloured digraphs,J. Combin. Theory Ser. B,33(1982) 271-275. · Zbl 0488.05036
[14] J.
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.