On the Complexity of Stacked Graphs Associated with Paths and Cycles

The complexity of a graph, defined as its number of spanning trees, serves as a key measure of network reliability. Stacked graphs constitute a significant and versatile class of graphs, formed by superimposing multiple copies of a base graph upon a shared central vertex set. Their inherent layered symmetry and structural regularity make them compelling models for a wide range of real-world networks, including multi-tier communication systems, hierarchical data networks, and resilient distributed architectures. Moreover, their systematic construction from well-known graph families renders the study of their complexity both mathematically rich and algorithmically meaningful. In this paper, we derive closed-form formulas for the complexity of several stacked graph families based on path- and cycle-based structures with a central vertex, including stacked fan and wheel graphs, stacked double fan and double wheel graphs, and stacked path flower, cycle flower, and gear graphs. The derivations are based on techniques from linear algebra, matrix theory, and Chebyshev polynomials.