On the Minimum Number of Spanning Trees in k‐Edge‐Connected Graphs |
| |
| Authors: | S. Ok C. Thomassen |
| |
| Affiliation: | DEPARTMENT OF APPLIED MATHEMATICS AND COMPUTER SCIENCES, TECHNICAL UNIVERSITY OF DENMARK, DENMARK |
| |
| Abstract: | We show that a k‐edge‐connected graph on n vertices has at least  spanning trees. This bound is tight if k is even and the extremal graph is the n‐cycle with edge multiplicities  . For k odd, however, there is a lower bound  , where  . Specifically,  and  . Not surprisingly, c3 is smaller than the corresponding number for 4‐edge‐connected graphs. Examples show that  . 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  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. |
| |
| Keywords: | spanning tree cubic graph edge connectivity |
|
|
spanning trees. This bound is tight if k is even and the extremal graph is the n‐cycle with edge multiplicities 
. For k odd, however, there is a lower bound 
, where 
. Specifically, 
and 
. Not surprisingly, c3 is smaller than the corresponding number for 4‐edge‐connected graphs. Examples show that 
. 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 
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.