1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On Q-Connected Chordal Graphs with Minimum Number of Spanning Trees

Published Online: 08 Jul 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 13 Dec 2020
Accepted: 07 Jun 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let k be the largest integer such that m(n-k)(n-k-1)2+qkq(n-1)m \ge {{\left( {n - k} \right)\left( {n - k - 1} \right)} \over 2} + qk \ge q\left( {n - 1} \right) 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-k2q2{{n - k} \over 2} \ge q \ge 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 HS(q, n, m)and HG. In addition, we give a sharp lower bound for the number of spanning trees of graphs in S(q, n, m).

Keywords

MSC 2010

[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.6148310.1109/26.61483Search in Google Scholar

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

[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-110.1007/s00373-012-1228-1Search in Google Scholar

[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.01010.1016/j.disc.2008.08.010Search in Google Scholar

[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-310.1016/0095-8956(74)90065-3Search in Google Scholar

[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-710.1016/0095-8956(72)90045-7Search in Google Scholar

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

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

[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.323022020610.1002/net.3230220206Search in Google Scholar

[10] N.C. Wormald, Counting labelled chordal graphs, Graphs Combin. 1 (1985) 193–200. https://doi.org/10.1007/BF0258294410.1007/BF02582944Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo