Complexity of some graphs generated by square

Abstract

Complexity plays a vital and significant role when designing communication networks (graphs). The more quality and perfect the network, the greater the number of trees spanning this network, which leads to greater possibilities of connection between two vertices, and this ensures good rigidity and resistance. In this work, we present nine network designs created by a square of different average degree 4, 6 and 8, then we deduce a simpler and evident formula expressing the number of spanning trees of these networks using some basic properties of orthogonal polynomials, block matrix analysis technique, and recurrence relations. In addition, we compute the entropy of each network and determine the best by comparing these designs using network entropy. Finally, we compare the entropy of spanning trees on our networks with other triangle and Apollonian networks and observe the entropy of our networks, which is the highest among the triangle and Apollonian networks studied.