10/01/1990 09:00 AM
Computer Science
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 edge-labeled directed graph with n vertices, write U^k_v for the universal cover of G, rooted at a vertex v and truncated at depth k . In this note we consider the smallest depth m for which isomorphism between U^m_v and U^m_w guarantees that U^k_v and U^k_w 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. Our result is an improvement over the previous result of n^2 due to Yamashita and Kameda. It applies immediately to graphs without edge-labels.
