zbMATH — the first resource for mathematics

On the minimum number of spanning trees in \(k\)-edge-connected graphs. (English) Zbl 1359.05023
Summary: We show that a \(k\)-edge-connected graph on \(n\) vertices has at least \(n(k/2)^{n-1}\) spanning trees. This bound is tight if \(k\) is even and the extremal graph is the \(n\)-cycle with edge multiplicities \(k/2\). For \(k\) odd, however, there is a lower bound \(c_k^{n-1}\), where \(c_k>k/2\). Specifically, \(c_3>1.77\) and \(c_5>2.75\). Not surprisingly, \(c_3\) is smaller than the corresponding number for 4-edge-connected graphs. Examples show that \(c_3\leq\sqrt{2+\sqrt{3}}\approx1.93\). However, we have no examples of 5-edge-connected graphs with fewer spanning trees than the \(n\)-cycle with all edge multiplicities (except one) equal to 3, which is almost 6-regular. We have no examples of 5-regular 5-edge-connected graphs with fewer than \(3.09^{n-1}\) spanning trees, which is more than the corresponding number for 6-regular 6-edge-connected graphs. The analogous surprising phenomenon occurs for each higher odd edge connectivity and regularity.

05C05 Trees
05C40 Connectivity
Full Text: DOI
[1] Barnette, The Many Facets of Graph Theory pp 27– (1969) · doi:10.1007/BFb0060102
[2] Brooks, The dissection of rectangles into squares, Duke Math J 7 pp 312– (1940) · Zbl 0024.16501 · doi:10.1215/S0012-7094-40-00718-9
[3] Diestel, Graph Theory (2010) · Zbl 1204.05001 · doi:10.1007/978-3-642-14279-6
[4] Kostochka, The number of spanning trees in graphs with a given degree sequence, Random Struct Algor 6 pp 269– (1995) · Zbl 0819.05032 · doi:10.1002/rsa.3240060214
[5] Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes, J Combin Theory Ser B 24 pp 202– (1978) · Zbl 0313.05114 · doi:10.1016/0095-8956(78)90021-7
[6] Mader, A reduction method for edge-connectivity in graphs, Ann Discrete Math 3 pp 145– (1978) · Zbl 0389.05042 · doi:10.1016/S0167-5060(08)70504-1
[7] S. Ok Aspects of the Tutte polynomial 2015
[8] M. Rubey Counting spanning trees 2000
[9] Thomassen, Resistances and currents in infinite electrical networks, J Combin Theory Ser B 49 pp 87– (1990) · Zbl 0706.94029 · doi:10.1016/0095-8956(90)90065-8
[10] V. K. Titov A constructive description of some classes of graphs 1975
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.