On q-connected chordal graphs with minimum number of spanning trees
Zbigniew R. Bogdanowicz · Discussiones Mathematicae Graph Theory · 2021
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-k 2 ≥ 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) < 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).