On the maximal number of spanning trees in cacti with given order
- Authors: Voblyi V.A.1, Kononenko D.A.1
-
Affiliations:
- All-Russian Institute for Scientific and Technical Information of Russian Academy of Sciences
- Issue: Vol 241 (2025)
- Pages: 13-17
- Section: Articles
- URL: https://journals.rcsi.science/2782-4438/article/view/312558
- DOI: https://doi.org/10.36535/2782-4438-2025-241-13-17
- ID: 312558
Cite item
Full Text
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.
About the authors
Vitalii Antonievich Voblyi
All-Russian Institute for Scientific and Technical Information of Russian Academy of SciencesDoctor of physico-mathematical sciences, no status
Dmitrii Andreevich Kononenko
All-Russian Institute for Scientific and Technical Information of Russian Academy of Sciences
References
- Воблый В. А., “О числе остовных деревьев в помеченном кактусе”, Прикл. дискр. мат. Приложение., 10 (2017), 139–140
- Воблый В. А., Кононенко Д. А., “Оценка надежности кактусных информационных сетей с заданным числом циклов”, Мат. XXI Междунар. семин. «Комбинаторные конфигурации и их приложения», Кропивницкий, 2019, 32–34
- Кудрявцев Л. Д., Краткий курс математического анализа, Наука, М., 1989
- Татт Ф., Теория графов, Мир, М., 1988
- Харари Ф., Теория графов, Мир, М., 1973
- Харари Ф., Палмер Э., Перечисление графов, Мир, М., 1977
- Atajan T., Inaba Y., “Network reliability analysis by counting the number of spanning trees”, Proc. IEEE Int. Symp. on Communications and Information Technology, 1 (2004), 601–604
- Fard N., Lee T., “Spanning tree approach in all-terminal network reliability expansion”, Comput. Commun., 24 (2004), 601–604
- Fernau H., Ryan J.F., Sugeng K. A., “A sum labeling for generalized fiendship graph”, Discr. Math., 308 (2008), 734–740
- Fu-Shang P. Tsen, Ting-Yi Sung, Men-Yang Lin, Myrvold W., “Finding the most vital edges wirh respect to the number of spanning trees”, IEEE Trans. Reliability., 24 (2001), 1348–1353
- Lam C. Y., Ip W. H., “An improved spanning tree approach for the reliability analysis of supply chain collaborative network”, Enterp. Inf. Syst., 6:4 (2012), 405–418
- Mertzios G. B., Unger W., “The friendship problem on graphs”, J. Multiple-Valued Logic Soft Comput., 27:2-3 (2014), 1–11
- Zarghami S. A., Gunawan I., Schultmann F., “Exact reliability evaluation of infrastructure networks using graph theory”, Qual. Reliab. Eng. Int., 36:2 (2019), 498–510
- Zhang Zhongzhi, Shuyang Gao, Lichao Chen, Shuigeng Zhou, Hongjuan Zhang, Jihong Guan, “Mapping Koch curves into scale-free small-world networks”, J. Phys. A: Math. Theor., 43 (2010), 395101
Supplementary files
