The number of spanning trees of cyclic snakes

Christian Barrientos

Abstract


A cyclic snake is a connected graph formed by connecting, by means of vertex amalgamation, a certain number of copies of the cycle Cn, in such a way that the i-th copy of Cn is connected with the (i+1)-th copy, resulting in a graph with maximum degree 4. Spanning trees of this type of graph can be easily found, but finding the number of nonisomorphic spanning trees of a given cyclic snake is a more challenging problem. In this work, we investigate the number of cyclic snakes formed with k copies of Cn, the number of spanning trees of any given cyclic snake. We also classified these trees according to their diameters. Finally, we study the morphology of the trees associated to the snakes where the distance between cut-vertices is a constant.


Keywords


cyclic snake, spanning tree

Full Text:

PDF

DOI: http://dx.doi.org/10.19184/ijc.2024.9.1.3

References

C. Barrientos, Graceful labelings of cyclic snakes, Ars Combin, 60(2001), 85--96.

F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278(1975), 322--335.

D. Moulton, Graceful labelings of triangular snakes, Ars Combin, 28(1989), 3--13.

A. Rosa, Cyclic Steiner triple systems and labelings of triangular cacti. Scientia, 5(1988) 87--95.

B. Y. Wu and K-M. Chao, Spanning Trees and Optimization Problems. Chapman & Hall/CRC, Boca Raton (2004).


Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats