On the Number of Synchronizing Colorings of Digraphs

DOI10.1007/978-3-319-22360-5_11MaRDI QIDQ2947415zbMATH OpenOpenAlexFDO

Authors Marek Szykuła, Vladimir V. Gusev

Publication date 23 September 2015

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.02133

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Formal languages and automata (68Q45)

Abstract: We deal with $k$-out-regular directed multigraphs with loops (called simply emph{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/k^d$, for every $dge1$ 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$.

Recommendations

• On synchronizing colorings and the eigenvectors of digraphs
• scientific article; zbMATH DE number 4019095
• On harmonious colorings of regular digraphs
• Synchronizing sequences for road colored digraphs
• Cliques and colorings in generalized Paley graphs and an approach to synchronization
• A note on total colourings of digraphs
• On the simultaneous edge coloring of graphs
• Colorings in digraphs from the spectral radius
• Colorings and spectral radius of digraphs
• scientific article; zbMATH DE number 4047751

Cites work

• A monotonicity formula for stationary biharmonic maps
• Depth-First Search and Linear Graph Algorithms
• Equivalence of topological Markov shifts
• Generating small automata and the Černý conjecture
• scientific article; zbMATH DE number 6861928 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• On the probability of being synchronizable
• P-NP threshold for synchronizing road coloring
• Practical graph isomorphism. II.
• Primitive digraphs with large exponents and slowly synchronizing automata
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Synchronizing Automata with Extremal Properties
• The dynamic stability of a rotating pre-twisted asymmetric cross-section Timoshenko beam subjected to lateral parametric excitation
• Černý's conjecture and the road colouring problem

Cited in

(5)

• Černý's conjecture and the road colouring problem
• scientific article; zbMATH DE number 5989958 (Why is no real title available?)
• A partially synchronizing coloring
• On synchronizing colorings and the eigenvectors of digraphs
• The Ordered and Colored Products in Analytic Combinatorics: Application to the Quantitative Study of Synchronizations in Concurrent Processes

This page was built for publication: On the Number of Synchronizing Colorings of Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947415)