Enumeration of spanning trees of middle graphs

摘要

Let G be a simple graph with n vertices and m edges, and Δ and δ the maximum degree and minimum degree of G. Suppose G′ is the graph obtained from G by attaching Δ−dG(v) pendent edges to each vertex v of G. Huang and Li (Bull. Aust. Math. Soc. 91(2015), 353–367) proved that if G is regular (i.e., Δ=δ,G=G′), then the middle graph of G, denoted by M(G), has 2m−n+1Δm−1t(G) spanning trees, where t(G) is the number of spanning trees of G. In this paper, we prove that t(M(G)) can be expressed in terms of the summation of weights of spanning trees of G with some weights on its edges. Particularly, we prove that if G is irregular (i.e., Δ ≠ δ), then t(M(G′))=2m−n+1Δm+k−1t(G), where k is the number of vertices of degree one in G′.