Forest embeddings in regular graphs of large girth

This paper deals with the enumeration of distinct embeddings (both induced and partial) of arbitrary graphs in regular graphs of large girth. A simple explicit recurrence formula is presented for the number of embeddings of an arbitrary forest F in an arbitrary regular graph G of sufficiently large girth. This formula (and hence the number of embeddings) depends only on the order and degree of regularity of G, and the degree sequence and component structure (multiset of component orders) of F. A concept called c-subgraph regularity is introduced which generalizes the familiar notion of regularity in graphs. (Informally, a graph is c-subgraph regular if its vertices cannot be distinguished on the basis of embeddings of graphs of order less than or equal to c.) A central result of this paper is that if G is regular and has girth g, then G is (g ? 1)-subgraph regular.