Finding the number and the entropy of spanning trees of a generalized class of self-similar fractal graphs

Counting the number of spanning trees in a large and complex network is a challenge problem. This problem is studied in different fields such as discrete mathematics, chemistry, physics, and theortical computer science. An explicit exact analytical expression for the number of spanning trees a class of planar, small-world and self-similar graphs is introduced in this paper. Firstly, we present the model growth mechanism which is based on two operations named link operation and C k attachment operation. The proposed model is self-similar fractal model G(k, t) motivated from the well-known Koch curve. Some topological properties, in terms of average degree, clustering coefficient, and degree distribution are studied. Based on the derived exact analytical expression for the total number of spanning trees of the proposed models, the entropies of spanning trees of the new networks G(k, t) are obtained and compared with the other network models with different average degrees, indicating the structural topology of the poposed model which describing this exponential growth of the number of the spanning trees with time steps