Premium
On the Minimum Number of Spanning Trees in k ‐Edge‐Connected Graphs
Author(s) -
Ok S.,
Thomassen C.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22026
Subject(s) - combinatorics , mathematics , spanning tree , enhanced data rates for gsm evolution , 1 planar graph , trémaux tree , discrete mathematics , graph , chordal graph , pathwidth , line graph , computer science , telecommunications
We show that a k ‐edge‐connected graph on n vertices has at least n ( k / 2 ) n − 1spanning 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 , wherec k > k / 2 . Specifically,c 3 > 1.77 andc 5 > 2.75 . Not surprisingly, c 3 is smaller than the corresponding number for 4‐edge‐connected graphs. Examples show thatc 3 ≤ 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 . 09 n − 1spanning 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.