Enumeration of spanning trees in prisms of some graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-4664Keywords:
complexity, recurrence relation, prism over a graph, Chebyshev polynomialsAbstract
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.
References
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. 3-4, pp. 229-243, 1987. https://doi.org/10.1080/00207168708803568
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. 1-14, 2014.
S. N. Daoud, “Number of spanning trees of different products of complete and complete bipartite graphs”, Mathematical Problems in Engineering, vol. 23, 2014. https://doi.org/10.1155/2014/965105
S. N. Daoud and K. Mohamed, “The complexity of Some Families of Cycle-Related Graphs”, Journal of Taibah University for science, vol. 11, no. 2, pp. 205-228, 2017. https://doi.org/10.1016/j.jtusci.2016.04.002
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 Publishing Company, 2014.
A. K. Kelmans and V. M. Chelnokov, “A certain polynomials of a graph and graphs with an extermal number of tres”, Journal of Combinatorial Theory, Series B, vol. 16, pp. 197-214, 1974. https://doi.org/10.1016/0095-8956(74)90065-3
G. Kirchhoff, “Ueber die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird”, Annalen der Physik und Chemie, vol. 72, pp. 497-508, 1847. https://doi.org/10.1002/andp.18471481202
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, vol. 6, no.1, pp. 65-75, 2016. https://doi.org/10.11948/2016006
Y. Zhang, X. Yong and M. Y. Golin, “Chebyshev polynomials and spanning trees formulas for circulant and related graphs”, Discrete Mathematics, vol. 298, no. 1, pp. 334-364, 2005. https://doi.org/10.1016/j.disc.2004.10.025
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, vol. 11, no. 4, pp. 4248-4283, 2021. https://doi.org/10.28919/jmcs/5533
Published
How to Cite
Issue
Section
Copyright (c) 2023 Mohamed Zeen El Deen
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
