The number of spanning trees in a superprism | [Discrete Mathematics Letters • 2024]

Author(s):

1. Zbigniew R. Bogdanowicz: CCDC Armaments Center,Picatinny, New Jersey 07806,USA

Abstract:

Let the vertices of two disjoint and equal length cycles be denoted u0; u1; : : : ; un 1 in the first cycle and v0; v1; : : : ; vn 1 in the second cycle for n 4. The superprism Pn is defined as the graph obtained by adding to these disjoint cycles all edges of the form uivi and uivi+2 (mod n). In this paper, it is proved that the number of spanning trees in Pn is n 23n 2.

Page(s): 66-73

DOI: 10.47443/dml.2024.004

Published: Journal: Discrete Mathematics Letters, Volume: 13, Issue: 0, Year: 2024

Keywords:

Spanning Trees , circulant graph , antiprism graph , prism graph , enumeration of trees

References:

[1] . .. det 66 1, : .

[2] . .. , (Corollary 3) : .

[3] Baron G.,Boesch F.,Prodinger H.,Tichy R.,J. Wang, R.,Bernardi O.,Boesch F. T.,Bogdanowicz Z. R.,Boesch F. T.,Prodinger H.,Cayley G. A.,Chen X.,Fu H. L.,Lo Y. H.,Perry K. E.,Rodger C. A.,Golin M. J.,Leung Y. C.,Nagl M. .2018 .Unhooking circulant graphs: a combinatorial method for counting spanning trees and other parameters. Q. J. Math. 23, 341 : 2343-2352.

[4] Kirchhoff G. .2004 .Ueber die Auflo¨sung der Gleichungeg, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Stro¨me gef u¨hrt wird. Ann. Phys. Chem, : 296-307.

[5] A. D. Mednykh I. A.,Mednykh I. A.,Read R. C.,Wilson R. J.,Schwenk A.,Bari F.,Harary F. .2004 .Computing the characteristic polynomial of a graph. Graphs and Combinatorics, Lecture Notes in Mathematics 406,, 342 : 261-270.

[6] Sedla J.,Sedla J.,Sedla J.,Hanani M. .1970 .´ ce˘k, On the skeleton of graph or digraph. Gordon and Breach, 94 : 111-115.

[7] York ,Wang G. J. F.,Yang C. S.,Zhang Y.,Yong X.,Golin M. J. .2005 .Chebyshev polynomials and spanning tree formulas for circulant and related graphs. Int. J. Comput. Math, 298 : 334-364.

Citations

Downloads

Views