Article in volume
Authors:
Title:
On $q$-connected chordal graphs with minimum number of spanning trees
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 1019-1032
Received: 2020-12-13 , Revised: 2021-06-07 , Accepted: 2021-06-07 , Available online: 2021-06-22 , https://doi.org/10.7151/dmgt.2414
Abstract:
Let $k$ be the largest integer such that $m \ge \frac{(n-k)(n-k-1)}{2}+qk
\ge 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 $\frac{n-k}{2}
\ge q \ge 2$. Let $t(G)$ be the number of spanning trees in graph $G$.
We identify $G \in S(q,n,m)$ such that $t(G) < t(H)$ for any $H$ that satisfies
$H \in S(q,n,m)$ and $H \ncong 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
References:
- 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 - Z.R. Bogdanowicz, Chordal $2$-connected graphs and spanning trees, J. Graph Theory 76 (2014) 224–235.
https://doi.org/10.1002/jgt.21761 - 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 - 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 - 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 - 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 - D.G. Luenberg, Linear and Nonlinear Programming, 2nd Ed. (Kluwer Academic-Reading, 2003).
- N. Mahadev and V. Peled, Threshold Graphs and Related Topics (Ann. Discrete Math. 56, North-Holland, Amstredam, 1995).
- 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 - N.C. Wormald, Counting labelled chordal graphs, Graphs Combin. 1 (1985) 193–200.
https://doi.org/10.1007/BF02582944
Close