Geodesic
On $q$-connected chordal graphs with minimum number of spanning trees
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1019-1032

Voir la notice de l'article provenant de la source Library of Science

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},
     publisher = {mathdoc},
     volume = {43},
     number = {4},
     year = {2023},
     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
PB  - mathdoc
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
%I mathdoc
%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/