On the Minimum Number of Spanning Trees in k-Edge-Connected Graphs

Seongmin Ok, Carsten Thomassen

Research output: Contribution to journalJournal articleResearchpeer-review

732 Downloads (Pure)

Abstract

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 ckn-1, where ck>k/2. Specifically, c3>1.77 and c5>2.75. Not surprisingly, c3 is smaller than the corresponding number for 4-edge-connected graphs. Examples show that c3≤ √2+√3≈1.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.09n-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.
Original languageEnglish
JournalJournal of Graph Theory
Volume84
Issue number3
Pages (from-to)286–296
Number of pages11
ISSN0364-9024
DOIs
Publication statusPublished - 2017

Keywords

  • Spanning trees
  • Cubic graph
  • Edge connectivity

Cite this