On the maximal number of spanning trees in cacti with given order

V. A. Voblyi, D. A. Kononenko

All-Russian Institute for Scientific and Technical Information of Russian Academy of Sciences, Moscow

Abstract: The number of spanning trees of a graph is an important characteristic of its reliability as a data transmission network. We found the maximal number of spanning trees in a cactus with a given number of vertices and also in a bipartite cactus with a given number of vertices. In particular, friendship graphs and Koch networks are extremal graphs.

Keywords: enumeration, labeled graph, spanning tree, cactus, bipartite cactus, extremal graph, fiendship graph, Koch network

UDC: 519.175.3

MSC: 05C30

DOI: 10.36535/2782-4438-2025-241-13-17