Universal covers of graphs: Isomorphism to depth n-1 implies isomorphism to all depths

Vertex- and edge-labeled digraphs have been used to model computer networks, and the universal covers of such graphs to describe what a processor in an anonymous network ‘knows’ about the network. If G is a connected vertex- and edge-labeled directed multigraph having n vertices, write for the universal cover of G, rooted at a vertex υ and truncated at depth k. This paper considers the smallest depth m for which isomorphism between and guarantees that and are isomorphic to all depths k, for w vertices in the universal cover of G. It shows that this m equals . Isomorphism to a depth smaller than does not insure isomorphisms to all depths. This result is an improvement over the previous result of due to Yamashita and Kameda. It applies immediately to graphs without edge labels, and improves by several previous results in anonymous computing. This paper will prove a general result about subtrees of universal covers of vertex- and edge-labeled digraphs, and derives as corollaries the above-mentioned results and an extension of a theorem due to Moore on the equivalence of states in finite-state machines.