Soliton graphs are studied in the context of a reduction procedure that simplies the structure of graphs without affecting the deterministic property of the corresponding automata. It is shown that an elementary soliton graph denes a deterministic automaton iff it reduces to a graph not containing even-length cycles. Based on this result, a general characterization is given for det..