Isomorphism of Binary Replacement Graphs: A Complete Classification of Keywords

In A New Combinatorial Interpretation of Partial Sums of m-Step Fibonacci Numbers, Bates et al. posed Open Problem 18: if two keywords give isomorphic binary replacement graphs at every word length, must one be obtained from the other by negation, reversal, and seminegation? We first establish criteria for nonisomorphism, then give a complete classification of keywords that produce isomorphic graphs at every word length. This classification answers Open Problem 18: compositions of the three operations do not cover all such cases. The PDF contains English and Russian versions of the manuscript. The LaTeX source is included.