Geodesic
On $q$-connected chordal graphs with minimum number of spanning trees
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1019-1032 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Let k be the largest integer such that m ≥(n-k)(n-k-1)2+qk ≥ q(n-1) for some positive integers n, m, q. Let S(q,n,m) be a set of all q-connected chordal graphs on n vertices and m edges for n-k2≥ q ≥ 2. Let t(G) be the number of spanning trees in graph G. We identify G ∈ S(q,n,m) such that t(G) lt; t(H) for any H that satisfies H ∈ S(q,n,m) and H G. In addition, we give a sharp lower bound for the number of spanning trees of graphs in S(q,n,m).
Keywords: chordal graph, spanning tree, enumeration of trees, threshold graph, minimum number of trees, shift transformation 
@article{DMGT_2023_43_4_a8,
     author = {Bogdanowicz, Zbigniew R.},
     title = {On $q$-connected chordal graphs with minimum number of spanning trees},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1019--1032},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a8/}
}
TY  - JOUR
AU  - Bogdanowicz, Zbigniew R.
TI  - On $q$-connected chordal graphs with minimum number of spanning trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1019
EP  - 1032
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a8/
LA  - en
ID  - DMGT_2023_43_4_a8
ER  - 
%0 Journal Article
%A Bogdanowicz, Zbigniew R.
%T On $q$-connected chordal graphs with minimum number of spanning trees
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1019-1032
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a8/
%G en
%F DMGT_2023_43_4_a8
Bogdanowicz, Zbigniew R. On $q$-connected chordal graphs with minimum number of spanning trees. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1019-1032. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a8/

[1] F.T. Boesch, A. Satyanarayana and C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004–2009. https://doi.org/10.1109/26.61483

[2] Z.R. Bogdanowicz, Chordal 2-connected graphs and spanning trees, J. Graph Theory 76 (2014) 224–235. https://doi.org/10.1002/jgt.21761

[3] Z.R. Bogdanowicz, On family of graphs with minimum number of spanning trees, Graphs Combin. 29 (2013) 1647–1652. https://doi.org/10.1007/s00373-012-1228-1

[4] Z.R. Bogdanowicz, Undirected simple connected graphs with minimum number of spanning trees, Discrete Math. 309 (2009) 3074–3082. https://doi.org/10.1016/j.disc.2008.08.010

[5] A.K. Kelmans and V.M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees, J. Combin. Theory Ser. B 16 (1974) 197–214. https://doi.org/10.1016/0095-8956(74)90065-3

[6] L. Lovász, A characterization of perfect graphs, J. Combin. Theory Ser. B 13 (1972) 95–98. https://doi.org/10.1016/0095-8956(72)90045-7

[7] D.G. Luenberg, Linear and Nonlinear Programming, 2nd Ed. (Kluwer Academic-Reading, 2003).

[8] N. Mahadev and V. Peled, Threshold Graphs and Related Topics (Ann. Discrete Math. 56, North-Holland, Amstredam, 1995).

[9] A. Satyanarayana, L. Schoppmann and C.L. Suffel, A reliability-improving graph transformation with applications to network reliability, Networks 22 (1992) 209–216. https://doi.org/10.1002/net.3230220206

[10] N.C. Wormald, Counting labelled chordal graphs, Graphs Combin. 1 (1985) 193–200. https://doi.org/10.1007/BF02582944