On the number of synchronizing colorings of digraphs

Abstract

We deal with k-out-regular directed multigraphs with loops (called simply digraphs). The edges of such a digraph can be colored by elements of some fixed k-element set in such a way that outgoing edges of every vertex have different colors. Such a coloring corresponds naturally to an automaton. The road coloring theorem states that every primitive digraph has a synchronizing coloring. In the present paper we study how many synchronizing colorings can exist for a digraph with n vertices. We performed an extensive experimental investigation of digraphs with small number of vertices. This was done by using our dedicated algorithm exhaustively enumerating all small digraphs. We also present a series of digraphs whose fraction of synchronizing colorings is equal to 1 − 1/kd, for every d ≥ 1 and the number of vertices large enough. On the basis of our results we state several conjectures and open problems. In particular, we conjecture that 1 − 1/k is the smallest possible fraction of synchronizing colorings, except for a single exceptional example on 6 vertices for k = 2. © Springer International Publishing Switzerland 2015.