The Hybrid Cerny-Road coloring problem is investigated for graphs with Hamiltonian paths. We prove that if an aperiodic, strongly connected digraph of costant outdegree with n vertices has an Hamiltonian path, then it admits a synchronizing coloring with a reset word of length 2(n - 2)(n - 1) + 1. The proof is based upon some new results concerning locally strongly transitive automata.
On the Hybrid Cerny-Road Coloring Problem and Hamiltonian Paths / A., Carpi; D'Alessandro, Flavio. - STAMPA. - 6224:(2010), pp. 124-135. (Intervento presentato al convegno 14th International Conference on Developments in Language Theory tenutosi a London, ON; Canada) [10.1007/978-3-642-14455-4_13].
On the Hybrid Cerny-Road Coloring Problem and Hamiltonian Paths
D'ALESSANDRO, Flavio
2010
Abstract
The Hybrid Cerny-Road coloring problem is investigated for graphs with Hamiltonian paths. We prove that if an aperiodic, strongly connected digraph of costant outdegree with n vertices has an Hamiltonian path, then it admits a synchronizing coloring with a reset word of length 2(n - 2)(n - 1) + 1. The proof is based upon some new results concerning locally strongly transitive automata.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
