On Spanning Trees And Resistance Distances In Almost Complete Multipartite Graphs

Let G be a connected edge-weighted graph with vertex set V(G),edge set E(G),and the weighted function ω:E(G)→R,which is equivalent to a network N(G)in which each edge e has a resistor with conductance ω(e)(i.e.,the resistance 1/ω(e)).For any two vertices u and v of G,the resistance distance between u and v is defined as the effective resistance between nodes u and v in the corresponding electrical network,denoted as RG(u,v).By using the principle of substitution,physicists found some local transformations such as series-parallel rules,(generalized)Delta-Wye transformation,which can be used to compute the resistance distances and the number of spanning trees of graphs.In this paper,we obtain the complete multipartite graph-blossomed star transformations in resistance and spanning tree versions.As applications,we first obtain the close formulae of resistance distances and the number of spanning trees in a complete multipartite graph adding a matching.We also give a unified technique to count spanning trees of almost complete multipartite graphs,which results in closed formulae to enumerate spanning trees of the almost complete s-partite graphs for s=2,3,4.Finally,we consider the problem to calculate the sum of weights of spanning trees in a type of almost complete bipartite weighted graphs.