Chordal 2-Connected Graphs and Spanning Trees

被引:4
作者
Bogdanowicz, Zbigniew R. [1 ]
机构
[1] Armament Res, Ctr Dev & Engn, Picatinny Arsenal, NJ 07806 USA
关键词
05C38; 05C45; minimization; shift transformation; chordal graph; threshold graph; spanning tree; enumeration of trees; NETWORK RELIABILITY;
D O I
10.1002/jgt.21761
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We present a transformation on a chordal 2-connected simple graph that decreases the number of spanning trees. Based on this transformation, we show that for positive integers n, m with n(n-1)/2 >= m >= 2n-3, the threshold graph Qn,m having n vertices and m edges that consists of an (n-k)-clique and k-1 vertices of degree 2 is the only graph with the fewest spanning trees among all 2-connected chordal graphs on n vertices and m edges.
引用
收藏
页码:224 / 235
页数:12
相关论文
共 9 条
  • [1] Undirected simple connected graphs with minimum number of spanning trees
    Bogdanowicz, Zbigniew R.
    [J]. DISCRETE MATHEMATICS, 2009, 309 (10) : 3074 - 3082
  • [2] NETWORK TRANSFORMATIONS AND BOUNDING NETWORK RELIABILITY
    BROWN, JI
    COLBOURN, CJ
    DEVITT, JS
    [J]. NETWORKS, 1993, 23 (01) : 1 - 17
  • [3] Enumeration of P4-free chordal graphs
    Castelo, R
    Wormald, N
    [J]. GRAPHS AND COMBINATORICS, 2003, 19 (04) : 467 - 474
  • [4] Kelmans A. K., 1974, Journal of Combinatorial Theory, Series B, V16, P197, DOI 10.1016/0095-8956(74)90065-3
  • [5] Lovasz L., 1972, Journal of Combinatorial Theory, Series B, V13, P95, DOI 10.1016/0095-8956(72)90045-7
  • [6] Luenberg, 2003, LINEAR NONLINEAR PRO
  • [7] Mahadev N., 1995, Annals of Discrete Mathematics, V56
  • [8] A RELIABILITY-IMPROVING GRAPH TRANSFORMATION WITH APPLICATIONS TO NETWORK RELIABILITY
    SATYANARAYANA, A
    SCHOPPMANN, L
    SUFFEL, CL
    [J]. NETWORKS, 1992, 22 (02) : 209 - 216
  • [9] COUNTING LABELED CHORDAL GRAPHS
    WORMALD, NC
    [J]. GRAPHS AND COMBINATORICS, 1985, 1 (02) : 193 - 200