Complexity of some graphs generated by square

Mohamed R. Zeen El Deen, Walaa A. Aboamer


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.

Full Text: PDF

Published: 2021-06-02

How to Cite this Article:

Mohamed R. Zeen El Deen, Walaa A. Aboamer, Complexity of some graphs generated by square, J. Math. Comput. Sci., 11 (2021), 4248-4283

Copyright © 2021 Mohamed R. Zeen El Deen, Walaa A. Aboamer. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Copyright ©2022 JMCS