Undirected Cyclic Graph With Generalized De Bruijn Spanning Tree To Map The Eulerian Tour Counts

This paper discussed the number of spanning trees in the undirected circulant graphs with odd degrees, giving an analytic eppres-sion, an asymptotic result and an effective method to calculate the numbers. Furthermore, the paper discussed the case of generalized de Bruijn digraphs , especially providing a simple result expression on the number of spanning trees and Eulerian tours in a special kind of generalized de Bruijn digraphs. Since the number of spanning trees in iterated line graphs are closed related with their original graphs, the numbers of spanning trees in iterated line graphs of above two special graphs can be thus obtained.