×

Chordal 2-connected graphs and spanning trees. (English) Zbl 1296.05112

Summary: 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 \geq m \geq 2n-3\), the threshold graph \(Q_{n,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.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
Full Text: DOI

References:

[1] Z. R.Bogdanowicz, Undirected simple connected graphs with minimum number of spanning trees, Discrete Math309 (2009), 3074-3082. · Zbl 1202.05021
[2] J.Brown, C.Colbourn, and J.Devitt, Network transformations and bounding network reliability, Networks23 (1993), 1-17. · Zbl 0780.90046
[3] R.Castelo and N. C.Wormald, Enumeration of P4‐free chordal graphs, Graphs Combin19 (2003), 467-474. · Zbl 1032.05067
[4] A. K.Kelmans, V. M.Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees, J Combin Theory SerB 16 (1974), 197-214. · Zbl 0277.05104
[5] L.Lovász, A Characterization of perfect graphs, J Combin Theory SerB 13 (1972), 95-98. · Zbl 0241.05107
[6] D. G.Luenberg, Linear and Nonlinear Programming, 2nd edn., Kluwer Academic, Reading, Norwell, MA, 2003. · Zbl 1134.90040
[7] N.Mahadev and V.Peled, Threshold graphs and related topics, Annals Discrete Math56 (1995), North‐Holland Publishing Co., Amsterdam. · Zbl 0852.05001
[8] A.Satyanarayana, L.Schoppmann, and C. L.Suffel, A reliability‐improving graph transformation with applications to network reliability, Networks22 (1992), 209-216. · Zbl 0756.90038
[9] N. C.Wormald, Counting labelled chordal graphs, Graphs Combin1 (1985), 193-200. · Zbl 0572.05035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.