On totally synchronizing graphs

A coloring of a finite $k$-out directed graph $G$ is viewed as a deterministic complete automaton with state set $V(G)$.

The graph $G$ is called \emph{totally synchronizing} if every coloring is synchronizing.

We prove that total synchronization imposes strong restrictions on symmetry: if $G$ is strongly connected and totally synchronizing, then $Aut(G)$ contains no semiregular element; in particular, if $|Aut(G)|$ is divisible by a prime $p>k$, then $G$ is not totally synchronizing.

We then give general constructions of strongly connected $k$-out graphs with prescribed quotients and prescribed automorphism group that are \emph{not} totally synchronizing.

On the quotient side, we relate graph congruences to strong lumpability of the uniform random walk on $G$ and introduce \emph{totally simple} graphs, characterized by the absence of nontrivial congruences.

In this setting we obtain a Perron--Frobenius sufficient condition for total synchronization: a strongly connected non-lumpable graph whose integer Perron--Frobenius eigenvector admits at most one nontrivial equipartition is totally synchronizing.

Finally, we show that deciding whether a primitive $k$-out graph admits a non-synchronizing coloring is NP-complete, resolving an open problem of Gusev--Szykuła, and prove NP-completeness of deciding whether a graph admits a nontrivial Eulerian lumping.