Please use this identifier to cite or link to this item:
|Title:||On the number of synchronizing colorings of digraphs|
|Authors:||Gusev, V. V.|
|Citation:||Gusev V. V. On the number of synchronizing colorings of digraphs / V. V. Gusev, M. Szykuła. — DOI 10.1007/978-3-319-22360-5_11 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2015. — Vol. 9223. — P. 127-139.|
|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.|
|Appears in Collections:||Научные публикации, проиндексированные в SCOPUS и WoS CC|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.