Enumeration of connected graph coverings

Abstract

The number of the isomorphism classes of n-fold coverings of a graph G is enumerated by the authors (Canad. J. Math. XLII (1990), 747-761) and Hofmeister (Discrete Math. 98 (1991), 275-183). But the enumeration of the isomorphism classes of connected n-fold coverings of a graph has not been studied except for n = 2. In this paper, we enumerate the isomorphism classes of connected n-fold coverings of a graph G for any n. As a consequence, we obtain a formula for finding the total number of conjugacy classes of subgroups of a given index of a finitely generated free group. (C) 1996 John Wiley & Sons, Inc.