On the Number of Synchronizing Colorings of Digraphs
(2015) CIAA 2015 - 20th International Conference on Implementation and Application of Automata — Location: Umea, Sweden (18.August.2015)
Files
chp3A1010072F978-3-319-22360-5_11.pdf
Open Access - Adobe PDF
- 426.45 KB
Details
- Authors
- 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.
- Affiliations
Citations
Gusev, V., & Szykula, M. (2015). On the Number of Synchronizing Colorings of Digraphs. Implementation and Application of Automata, CIAA 2015, p. 127-139. https://doi.org/10.1007/978-3-319-22360-5_11