- Tytuł:
- On the Minimum Number of Spanning Trees in Cubic Multigraphs
- Autorzy:
- Bogdanowicz, Zbigniew R.
- Powiązania:
- https://bibliotekanauki.pl/articles/32083837.pdf
- Data publikacji:
- 2020-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
cubic multigraph
spanning tree
regular graph
enumeration - Opis:
- Let G2n, H2n be two non-isomorphic connected cubic multigraphs of order 2n with parallel edges permitted but without loops. Let t(G2n), t (H2n) denote the number of spanning trees in G2n, H2n, respectively. We prove that for n ≥ 3 there is the unique G2n such that t(G2n) < t(H2n) for any H2n. Furthermore, we prove that such a graph has t(G2n) = 522n−3 spanning trees. Based on our results we give a conjecture for the unique r-regular connected graph H2n of order 2n and odd degree r that minimizes the number of spanning trees.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 149-159
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł