Research article

On the number of spanning trees in the Cartesian product of star graphs and certain well-known graphs

  • Published: 17 November 2026
  • MSC : 05C05, 05C50

  • 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

    Related Papers:

  • 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

  • Reader Comments
  • © 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)

Metrics

Article views(5) PDF downloads(0) Cited by(0)

Article outline

Figures and Tables

Tables(11)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog