Enumeration of spanning trees in prisms of some graphs

• Zeen El Deen, Mohamed ^[1]
  1. [1] Suez University

     Suez University

     Egipto

     
• Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 42, Nº. 2, 2023, págs. 339-391
• Idioma: inglés
• DOI: 10.22199/issn.0717-6279-4664
• Enlaces
  • Texto completo
• Resumen

  • In graph theory, a prism over a graph G is the cartesian product of the graph G with P₂. The purpose of this work is to investigate the complexity of the prisms of some path and cycle-related graphs. In particular, we obtain simpler and more explicit formulas for the complexity of a special class of prisms of path-related graphs: fan graph, ladder graph, the composition Pn[P₂] graph, and book graph. Moreover, we obtain straightforward formulas for the complexity of a special class of prisms of cycle-related graphs: wheel graph, gear graph, prism graph, n−crossed prism graph, mirror graph M(Cn) of even cycle Cn, twisted prism, total graph T(Cn) of the cycle Cn, the friendship graph, the flower graph, and planner sunflower graph. These closed formulas are deduced using some basic properties of block matrix, recurrence relation, eigenvalues of circulant matrices, and orthogonal polynomials.

• Referencias bibliográficas
  • R. B. Bapat, Graphs and matrices. New York: Springer, 2010.
  • N. L. Biggs, Algebraic Graph Theory, 2nd. Cambridge, U.K.: Cambridge University Press, 1993.
  • F. T. Boesch and Z. R. Bogdanowicz, “The number of spanning tres in a prism”, International Journal of Computer Mathematics, vol. 21, nos....
  • F. T. Boesch and H. Prodinger, “Spanning tree formulas and chebyshev polynomials”, Graphs and Combinatorics, vol. 2, pp. 191-200, 1986. https://doi.org/10.1007/bf01788093
  • J. A. Bondy and U. S. R. Murty, Graph Theory. New York: Springer-Verlag, 2008.
  • A. Bose and K. Saha, Random Circulant Matrices. Taylor and Francis Group, 2019.
  • L. Clark, “On the enumeration of multipartite spanning trees of the complete graph”, Bulletin of the ICA, vol. 38, pp. 50-60, 2003.
  • S. N. Daoud, “Generating formulas of the number of spanning trees of some special graphs”, The European Physical Journal Plus, vol. 129, pp....
  • S. N. Daoud, “Number of spanning trees of different products of complete and complete bipartite graphs”, Mathematical Problems in Engineering,...
  • S. N. Daoud and K. Mohamed, “The complexity of Some Families of Cycle-Related Graphs”, Journal of Taibah University for science, vol. 11,...
  • S. N. Daoud, “Complexity of products of some complete and complete bipartite graphs”, Journal of Applied Mathematics, vol. 2013, 2013. https://doi.org/10.1155/2013/673270
  • D. J. Gross, T. J. Saccoman and L. C. Suffel, Spanning Tree Results For Graphs And Multigraphs: A Matrix-theoretic Approach. World Scientific...
  • A. K. Kelmans and V. M. Chelnokov, “A certain polynomials of a graph and graphs with an extermal number of tres”, Journal of Combinatorial...
  • G. Kirchhoff, “Ueber die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt...
  • J. B. Liu and S. N. Daoud, “The Complexity of Some Classes of Pyramid Graphs Created from a Gear Graph”, Symmetry, vol. 10, 689, 2018. https://doi.org/10.3390/sym10120689
  • J. C. Mason and D. C. Handscomb, Chebyshev Polynomials. Chapman and Hall/CRC, 2003.
  • M. Marcus, A Servy of Matrix Theory and Matrix Inequalities. Boston: Allyn and Bacon Inc., 1964.
  • J. Sedlacek, Lucas number in graph theory, In Mathematics (Geometry and Graph theory) (chech). Prague: University Karlova, 1970.
  • W. G. Sun, S. Wang and J. Zhang, “Counting spanning trees in a prism and anti-prism graphs”, Journal of Applied Analysis and Computation,...
  • Y. Zhang, X. Yong and M. Y. Golin, “Chebyshev polynomials and spanning trees formulas for circulant and related graphs”, Discrete Mathematics,...
  • H. N. V. Temperley, Graph theory and applications. Ellis Horwood series in mathematics and its applications. Chichester; Halsted Press, 1981.
  • M. R. Zeen El Deen and W. A. Aboamer, “Complexity of some duplicating networks”, IEEE Access, vol. 9, pp. 56736-56756, 2021, https://doi.org/10.1109/ACCESS.2021.3059048
  • M. R. Zeen El Deen and W. A. Aboamer, “Complexity of some graphs generated by a square”, Journal of Mathematical and Computational Science,...