Abstract :
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 Ukv for the universal cover of G, rooted at a vertex v and truncated at depth k. In this paper we consider the smallest depth m for which isomorphism between Umv and Umw guarantees that Ukv and Ukw are isomorphic to all depths k, for v, w vertices in the universal cover of G. We show that this m equals n − 1. Isomorphism to a depth smaller than n − 1 does not insure isomorphism to all depths. This result is an improvement over the previous result of n2 due to Yamashita and Kameda. It applies immediately to graphs without edge labels, and improves by O(n) several previous results in anonymous computing.
In this paper we will prove a general result about subtrees of universal covers of vertex-and edge-labeled digraphs, and derive as corollaries the above-mentioned result and an extension of a theorem due to Moore on the equivalence of states in finite-state machines.
