Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650985 | Discrete Mathematics | 2007 | 14 Pages |
Let D be a digraph and let G be a multidigraph whose arcs are colored with the vertices of D. A walk, W, in G is a D-walk if the consecutive colors encountered on W also form a walk in D . A set S⊆V(G)S⊆V(G) is a D-sink if any x∈V(G)-Sx∈V(G)-S reaches some y∈Sy∈S on a D-walk. We say S is D-independent (resp. independent) if no two vertices of S have a D -walk (resp. have an arc) between them. Let D∈B2D∈B2 (resp. D∈B3D∈B3) if any finite D arc-colored digraph G always has an independent (resp. D-independent) D -sink, and let D∈B1D∈B1 if any finite D arc-colored tournament always has a 1-point D-sink. Sands et al. [On monochromatic paths in edge-colored digraphs, J. Combin. Theory Ser. B 33 (1982) 271–275.] showed that if D has vertex set {red,blue}{red,blue} and arcs (red,red)(red,red), (blue,blue)(blue,blue) then D∈B3D∈B3, a D-walk then being just a monochromatic walk.Here we give a classification of B2B2, and make inroads in the classification of B3B3 and B1B1, as well we prove the strict containment B3⊊B2⊊B1B3⊊B2⊊B1. Finally, we generalize these problems by considering D to be an automaton and replacing D by the language accepted by D.