On the number of spanning trees of some irregular line graphs

摘要

Let G be a 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. It is well known that if G is regular (i.e., δ = δ, G = ~(G ')), then the line graph of G, denoted by L(G), has ~(2m -n +1δm -n -1)(G) spanning trees, where t(G) is the number of spanning trees of G. In this paper, we prove that if G is irregular (i.e., δ ≠ δ), then t(L(~(G '))) = ~(2m -n +1δm +s -n -1)t(G), where s is the number of vertices of degree one in G '.