The Cartesian product is a fundamental construction in graph theory that builds complex structures, such as grids and hypercubes, from simpler components. Many graph parameters, including the diameter and various topological indices used in mathematical chemistry, can be computed from the properties of the factors. In this paper, we studied the complexity, that is, the number of spanning trees, of the Cartesian product of a star graph with several important families of graphs. We first proved a general reduction: For any connected graph, the number of spanning trees of its product with a star was determined by two determinants of a shifted Laplacian matrix of that graph. Using this reduction together with linear algebra, block-matrix factorizations, and Chebyshev polynomials, we derived explicit closed-form formulas when the second factor is a path, cycle, complete graph, complete bipartite graph, fan, wheel, ladder, prism, Möbius ladder, gear graph, or hypercube.
Citation: Salama Nagy Daoud, Ahmad Asiri. On the number of spanning trees in the Cartesian product of star graphs and certain well-known graphs[J]. AIMS Mathematics, 2026, 11(11): 38185-38219. doi: 10.3934/math.20261475
The Cartesian product is a fundamental construction in graph theory that builds complex structures, such as grids and hypercubes, from simpler components. Many graph parameters, including the diameter and various topological indices used in mathematical chemistry, can be computed from the properties of the factors. In this paper, we studied the complexity, that is, the number of spanning trees, of the Cartesian product of a star graph with several important families of graphs. We first proved a general reduction: For any connected graph, the number of spanning trees of its product with a star was determined by two determinants of a shifted Laplacian matrix of that graph. Using this reduction together with linear algebra, block-matrix factorizations, and Chebyshev polynomials, we derived explicit closed-form formulas when the second factor is a path, cycle, complete graph, complete bipartite graph, fan, wheel, ladder, prism, Möbius ladder, gear graph, or hypercube.
| [1] |
D. M. Cvetković, M. Doob, H. Sachs, Spectra of graphs: theory and applications, 3 Eds., Heidelberg: Huthig Pub Ltd., 1995. |
| [2] |
D. L. Applegate, R. E. Bixby, V. Chvátal, W. J. Cook, The traveling salesman problem: a computational study, Princeton, NJ: Princeton University Press, 2006. |
| [3] |
R. P. Singh, Vandana, Application of graph theory in computer science and engineering, International Journal of Computer Applications, 104 (2014), 10–13. https://doi.org/10.5120/18165-9025 doi: 10.5120/18165-9025
|
| [4] |
N. Deo, Graph theory with applications to engineering and computer science, Englewood Cliffs, NJ: Prentice-Hall, 1974. |
| [5] |
P. Erdős, D. F. Hsu, Distributed loop network with minimum transmission delay, Theor. Comput. Sci. , 100 (1992), 223–241. https://doi.org/10.1016/0304-3975(92)90370-U doi: 10.1016/0304-3975(92)90370-U
|
| [6] |
G. R. Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. -Berlin, 148 (1847), 497–508. https://doi.org/10.1002/andp.18471481202 doi: 10.1002/andp.18471481202
|
| [7] |
A. Cayley, A theorem on trees, In: The collected mathematical papers, Cambridge: Cambridge University Press, 2009, 26–28. https://doi.org/10.1017/CBO9780511703799.010 |
| [8] |
M. Fiedler, J. Sedláček, O W-basích orientovaných grafů, Časopis pro pěstování matematiky, 83 (1958), 214–225. |
| [9] |
R. P. Lewis, The number of spanning trees of a complete multipartite graph, Discrete Math., 197–198 (1999), 537–541. https://doi.org/10.1016/S0012-365X(99)90111-5 doi: 10.1016/S0012-365X(99)90111-5
|
| [10] |
S. N. Daoud, Number of spanning trees in different products of complete and complete tripartite graphs, Ars Comb. , 139 (2018), 85–103. |
| [11] |
B. Myers, Number of spanning trees in a wheel, IEEE Transactions on Circuit Theory, 18 (1971), 280–282. https://doi.org/10.1109/TCT.1971.1083273 doi: 10.1109/TCT.1971.1083273
|
| [12] |
J. Sedláček, On the skeletons of a graph or digraph, In: Combinatorial structures and their applications, New York: Gordon and Breach, 1970,387–391. |
| [13] |
F. T. Boesch, Z. R. Bogdanowicz, The number of spanning trees in a prism, Int. J. Comput. Math. , 21 (1987), 229–243. https://doi.org/10.1080/00207168708803568 doi: 10.1080/00207168708803568
|
| [14] |
J. Sedláček, On the number of spanning trees of finite graphs, Časopis pro pěstování matematiky, 94 (1969), 217–221. https://doi.org/10.21136/CPM.1969.117654 doi: 10.21136/CPM.1969.117654
|
| [15] |
Z. R. Bogdanowicz, Formulas for the number of spanning trees in a fan, Applied Mathematical Sciences, 2 (2008), 781–786. |
| [16] |
S. N. Daoud, K. Mohamed, The complexity of some families of cycle-related graphs, J. Taibah Univ. Sci. , 11 (2017), 205–228. https://doi.org/10.1016/j.jtusci.2016.04.002 doi: 10.1016/j.jtusci.2016.04.002
|
| [17] |
O. Bernardi, On the spanning trees of the hypercube and other products of graphs, Electron. J. Comb. , 19 (2012), #P51. |
| [18] |
A. K. Kelmans, V. M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees, J. Comb. Theory B, 16 (1974), 197–214. https://doi.org/10.1016/0095-8956(74)90065-3 doi: 10.1016/0095-8956(74)90065-3
|
| [19] |
H. N. V. Temperley, Graph theory and applications: Ellis Horwood series in mathematics and its applications, Chichester: Ellis Horwood, 1981. |
| [20] |
J. A. Bondy, U. S. R. Murty, Graph Theory, Berlin, Germany: Springer, 2008. https://doi.org/10.1007/978-1-84628-970-5 |
| [21] |
S. N. Daoud, The deletion–contraction method for counting the number of spanning trees of graphs, Eur. Phys. J. Plus, 130 (2015), 217. https://doi.org/10.1140/epjp/i2015-15217-y doi: 10.1140/epjp/i2015-15217-y
|
| [22] |
E. Teufl, S. Wagner, On the number of spanning trees on various lattices, J. Phys. A: Math. Theor. , 43 (2010), 415001. https://doi.org/10.1088/1751-8113/43/41/415001 doi: 10.1088/1751-8113/43/41/415001
|
| [23] |
S. N. Daoud, W. Saleh, Complexity trees of the sequence of some nonahedral graphs generated by triangle, Heliyon, 6 (2020), e04786. https://doi.org/10.1016/j.heliyon.2020.e04786 doi: 10.1016/j.heliyon.2020.e04786
|
| [24] |
S. D. Nikolopoulos, L. Palios, C. Papadopoulos, Counting spanning trees using modular decomposition, Theor. Comput. Sci., 526 (2014), 41–57. https://doi.org/10.1016/j.tcs.2014.01.012 |
| [25] |
R. Balakrishnan, K. Ranganathan, A textbook of graph theory, 2 Eds., New York: Springer, 2012. https://doi.org/10.1007/978-1-4614-4529-6 |