Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102324
Title: On the number of synchronizing colorings of digraphs
Authors: Gusev, V. V.
Szykuła, M.
Issue Date: 2015
Publisher: Springer Verlag
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.
Keywords: AUTOMATA THEORY
COLORING
GRAPH THEORY
SYNCHRONIZATION
EXPERIMENTAL INVESTIGATIONS
K ELEMENTS
MULTIGRAPHS
PRIMITIVE DIGRAPHS
DIRECTED GRAPHS
URI: http://hdl.handle.net/10995/102324
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84951745267
PURE ID: 569188
bc9d385a-ae4b-418f-b68c-0e1b48beaee2
ISSN: 3029743
ISBN: 9783319223599
DOI: 10.1007/978-3-319-22360-5_11
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84951745267.pdf189,72 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.