Undirected simple connected graphs with minimum number of spanning trees |
| |
Authors: | Zbigniew R. Bogdanowicz |
| |
Affiliation: | Armament Research, Development and Engineering Center, Picatinny, NJ 07806, USA |
| |
Abstract: | We show that for positive integers n, m with n(n−1)/2≥m≥n−1, the graph Ln,m having n vertices and m edges that consists of an (n−k)-clique and k−1 vertices of degree 1 has the fewest spanning trees among all connected graphs on n vertices and m edges. This proves Boesch’s conjecture [F.T. Boesch, A. Satyanarayana, C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004-2009]. |
| |
Keywords: | Undirected simple graph Spanning tree Enumeration |
本文献已被 ScienceDirect 等数据库收录! |
|