Enumeration of spanning trees containing a perfect matching in linear polygonal chains

Jingchao Lai and Rongkun Zhu

Applied Mathematics and Computation, 2024, vol. 479, issue C

Abstract: The enumerative problem of spanning trees of graphs is one of the fundamental problems in the field of graph theory, which has attracted the attention of mathematicians and physicists. For a connected graph G, let T be a spanning tree of G. In this paper, we call T to be a pm-tree of G if T contains a perfect matching. Recently, Li and Yan (Applied Mathematics and Computation, 456 (2023), 128125.) gave an explicit expression for the number of pm-trees in linear hexagonal chains on the plane, cylinder and Möbius strip, respectively. In this paper, we extend the results above and obtain the explicit formula for the number of pm-trees in linear polygonal chains with n polygons of 4k+2 vertices on the plane, cylinder and Möbius strip, respectively.

Keywords: Spanning tree; Pm-tree; Linear polygonal chains; Perfect matching (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324003436
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:479:y:2024:i:c:s0096300324003436

DOI: 10.1016/j.amc.2024.128882

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().