Науковий вісник Ужгородського університету. Серія: Математика і інформатика (Dec 2017)
TRANSITION GRAPHS OF ITERATIONS OF INITIAL (2, 2)-AUTOMATA
Abstract
The iterations of an automaton A naturally produces a sequence of nite graphs GA(n) which describe the transitions in A(n) = A ◦ A ◦ . . . ◦ A (n times). We consider combinatorial properties of the graphs GA(n) for initial invertible automata with two states over the binary alphabet. We compute the chromatic number and girth of the graphs GA(n) and show that all of them are imbalance graphic.