The number of spanning trees in \(K_n\)-complement of a bipartite graph. (English) Zbl 07925634
Summary: For a subgraph \(G\) of a complete graph \(K_n\), the \(K_n\)-complement of \(G\), denoted by \(K_n -G\), is the graph obtained from \(K_n -G\) by removing all the edges of \(G\). In this paper, we express the number of spanning trees of the \(K_n\)-complement \(K_n -G\) of a bipartite graph \(G\) in terms of the determinant of the biadjcency matrices of all induced balanced bipartite subgraphs of \(G\), which are nonsingular, and we derive formulas of the number of spanning trees of \(K_n -G\) for various important classes of bipartite graphs \(G\), some of which generalize some previous results.
References:
| [1] | Aggarwal, KK; Suresh, R., Reliability evaluation in computer-communication networks, IEEE Trans. Reliab., 30, 1, 32-35, 1981 · Zbl 0456.90026 · doi:10.1109/TR.1981.5220952 |
| [2] | Bedrosian, SD, Formulas for the number of trees in certain incomplete graphs, J. Franklin Inst., 289, 67-69, 1970 · Zbl 0297.05125 · doi:10.1016/0016-0032(70)90261-9 |
| [3] | Boesch, FT, On unreliability polynomials and graph connectivity in reliable network synthesis, J. Graph Theory, 10, 3, 339-352, 1986 · Zbl 0699.90041 · doi:10.1002/jgt.3190100311 |
| [4] | Borovićanin, B.; Gutman, I.; Cvetković, D.; Gutman, I., Nullity of graphs, Applications of Graph Spectra, 107-122, 2009, Belgrade: Zbornik Radova, Belgrade · Zbl 1249.05243 |
| [5] | Cheng, SJ; Chen, WX; Yan, WG, Counting spanning trees in almost complete multipartite graphs, J. Algebraic Combin., 56, 773-783, 2022 · Zbl 1498.05130 · doi:10.1007/s10801-022-01131-4 |
| [6] | Chung, KL; Yan, WM, On the number of spanning trees of a multi-complete/star related graph, Inform. Process. Lett., 76, 113-119, 2000 · Zbl 1339.05189 · doi:10.1016/S0020-0190(00)00135-6 |
| [7] | Colbourn, CJ, The Combinatorics of Network Reliability, 1987, New York: Oxford University Press, New York |
| [8] | Collings, BJ, Characteristic polynomials by diagonal expansion, Amer. Statist., 37, 3, 233-235, 1983 · doi:10.1080/00031305.1983.10483111 |
| [9] | Dhar, D., Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 14, 1613-1616, 1990 · Zbl 0943.82553 · doi:10.1103/PhysRevLett.64.1613 |
| [10] | Dong, FM; Ge, J., Counting spanning trees in a complete bipartite graph which contain a given spanning forest, J. Graph Theory, 101, 79-94, 2022 · Zbl 1522.05200 · doi:10.1002/jgt.22812 |
| [11] | Dong, FM; Yan, WG, Expression for the number of spanning trees of line graphs of arbitrary connected graphs, J. Graph Theory, 85, 74-93, 2017 · Zbl 1365.05249 · doi:10.1002/jgt.22048 |
| [12] | Ehrenborg, R., The number of spanning trees of the Bruhat graph, Adv. Appl. Math., 125, 2021 · Zbl 1461.05110 · doi:10.1016/j.aam.2020.102150 |
| [13] | Ge, J., Effective resistance and spanning trees in the complete bipartite graph plus a matching, Discrete Appl. Math., 305, 145-153, 2021 · Zbl 1485.05043 · doi:10.1016/j.dam.2021.09.008 |
| [14] | Ge, J.; Dong, F., Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs, Discrete Appl. Math., 283, 542-554, 2020 · Zbl 1442.05049 · doi:10.1016/j.dam.2020.02.002 |
| [15] | Gilbert, B.; Myrvold, W., Maximizing spanning trees in almost complete graphs, Networks, 30, 23-30, 1997 · Zbl 0882.05051 · doi:10.1002/(SICI)1097-0037(199708)30:1<23::AID-NET3>3.0.CO;2-N |
| [16] | Gong, H.; Jin, X., A simple formula for the number of spanning trees of line graphs, J. Graph Theory, 88, 294-301, 2018 · Zbl 1395.05081 · doi:10.1002/jgt.22212 |
| [17] | Khodakhast, B., On the determinant of bipartite graphs, Discret. Math., 313, 21, 2446-2450, 2013 · Zbl 1279.05044 · doi:10.1016/j.disc.2013.07.006 |
| [18] | Kirchhoff, G., Über die auflösung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird, Annu. Rev. Phys. Chem., 72, 497-508, 1847 · doi:10.1002/andp.18471481202 |
| [19] | Klee, S.; Stamps, MT, Linear algebraic techniques for spanning tree enumeration, Amer. Math. Monthly, 127, 4, 297-307, 2020 · Zbl 1437.05106 · doi:10.1080/00029890.2020.1708171 |
| [20] | Moon, W.; Harary, F., Enumerating labeled trees, Graph Theory and Theoretical Physics, 261-271, 1967, London: Academic Press, London · Zbl 0202.55602 |
| [21] | Nikolopoulos, SD; Papadopoulos, C., The number of spanning trees in \(K_n\)-complements of quasi-threshold graphs, Graphs Combin., 20, 383-397, 2004 · Zbl 1054.05058 · doi:10.1007/s00373-004-0568-x |
| [22] | Nikolopoulos, SD; Papadopoulos, C., On the number of spanning trees of \(K^m_n\pm G\) graphs, Discrete Math. Theor. Comput. Sci., 8, 235-248, 2006 · Zbl 1153.05308 · doi:10.46298/dmtcs.364 |
| [23] | Nikolopoulos, SD; Rondogiannis, P., On the number of spanning trees of multi-star related graphs, Inform. Process. Lett., 65, 183-188, 1998 · Zbl 1339.05191 · doi:10.1016/S0020-0190(98)00008-8 |
| [24] | Noh, JD; Rieger, H., Random walks on complex networks, Phys. Rev. Lett., 92, 11, 2004 · doi:10.1103/PhysRevLett.92.118701 |
| [25] | Oboudi, MR, Bipartite graphs with at most six non-zero eigenvalues, Ars Math. Contemp., 11, 3151-325, 2016 · Zbl 1355.05158 · doi:10.26493/1855-3974.749.264 |
| [26] | O’Neil, PV, The number of trees in a certain network, Notices Amer. Math. Soc., 10, 569, 1963 |
| [27] | O’Neil, PV, Enumeration of spanning trees in certain graphs, IEEE Trans. Circuit Theory, 17, 2, 250, 1970 · doi:10.1109/TCT.1970.1083075 |
| [28] | Sciriha, I.; Alavi, Y.; Lick, DR; Schwenk, A., Combinatorics, On the rank of graphs, Combinatorics, Graph Theory, and Algorithms II, 769-778, 1999, Kalamazoo: New Issues Press, Kalamazoo |
| [29] | Shrock, R.; Wu, FY, Spanning trees on graphs and lattices in d dimensions, J. Phys. A, 33, 3881-3902, 2000 · Zbl 0949.05041 · doi:10.1088/0305-4470/33/21/303 |
| [30] | Temperley, HNV, On the mutual cancellation of cluster integrals in Mayer’s fugacity series, Proc. Phys. Soc., 83, 3-16, 1964 · doi:10.1088/0370-1328/83/1/302 |
| [31] | Weinberg, L., Number of trees in a graph, Proc. IRE, 46, 1954-1955, 1958 |
| [32] | Wu, FY, The Potts model, Rev. Modern Phys., 54, 1, 235-268, 1982 · doi:10.1103/RevModPhys.54.235 |
| [33] | Yan, WG, On the number of spanning trees of some irregular line graphs, J. Combin. Theory Ser. A, 120, 1642-1648, 2013 · Zbl 1314.05040 · doi:10.1016/j.jcta.2013.06.005 |
| [34] | Yan, WM; Myrnold, W.; Chung, KL, A formula for the number of spanning trees of a multi-star related graph, Inform. Process. Lett., 68, 295-298, 1998 · Zbl 1339.05192 · doi:10.1016/S0020-0190(98)00175-6 |
| [35] | Zhang, YP; Yong, XR; Golin, MJ, Chebyshev polynomials and spanning tree formulas for circulant and related graphs, Discrete Math., 298, 334-364, 2005 · Zbl 1070.05029 · doi:10.1016/j.disc.2004.10.025 |
| [36] | Zhou, J.; Bu, CJ, The enumeration of spanning tree of weighted graphs, J. Algebraic Combin., 54, 75-108, 2021 · Zbl 1470.05082 · doi:10.1007/s10801-020-00969-w |
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.
