Undirected simple connected graphs with minimum number of spanning trees

被引：12
作者：
Bogdanowicz, Zbigniew R. [1 ]
机构：
[1] Armament Res Dev & Engn Ctr, Picatinny Arsenal, NJ 07806 USA
来源：
DISCRETE MATHEMATICS | 2009年 / 309卷 / 10期
关键词：
Undirected simple graph; Spanning tree; Enumeration; MAXIMUM NUMBER; NETWORK RELIABILITY;
D O I：
10.1016/j.disc.2008.08.010
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that for positive integers n, m with n(n-1)/2 >= m >= n-1, the graph L(n,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]. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：3074 / 3082
页数：9
相关论文
共 14 条
  • [1] LEAST RELIABLE NETWORKS AND THE RELIABILITY DOMINATION
    BOESCH, FT
    SATYANARAYANA, A
    SUFFEL, CL
    [J]. IEEE TRANSACTIONS ON COMMUNICATIONS, 1990, 38 (11) : 2004 - 2009
  • [2] Bogdanowicz Z., 1985, THESIS STEVENS I TEC
  • [3] NETWORK TRANSFORMATIONS AND BOUNDING NETWORK RELIABILITY
    BROWN, JI
    COLBOURN, CJ
    DEVITT, JS
    [J]. NETWORKS, 1993, 23 (01) : 1 - 17
  • [4] Godsil C., 2001, ALGEBRAIC GRAPH THEO
  • [5] Harary F., 1969, Graph Theory
  • [6] Kelmans A. K., 1974, Journal of Combinatorial Theory, Series B, V16, P197, DOI 10.1016/0095-8956(74)90065-3
  • [7] Kelmans AK, 1996, RANDOM STRUCT ALGOR, V9, P177, DOI 10.1002/(SICI)1098-2418(199608/09)9:1/2<177::AID-RSA11>3.0.CO
  • [8] 2-L
  • [9] ON GRAPHS WITH RANDOMLY DELETED EDGES
    KELMANS, AK
    [J]. ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1981, 37 (1-3): : 77 - 88
  • [10] Luenberg, 2003, LINEAR NONLINEAR PRO
12