On the number of spanning trees of some irregular line graphs

Let G be a graph with n vertices and m edges and Delta and delta the maximum degree and minimum degree of G. Suppose G' is the graph obtained from G by attaching Delta - d(G)(v) pendent edges to each vertex v of G. It is well known that if G is regular (i.e., Delta = delta, G = G'), then the line graph of G, denoted by L(G), has 2(m-n+1) Delta(m-n-1) t(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., Delta not equal delta), then t(L(G'))= 2(m-n+1)) Delta(m+s-n-1) t(G), where s is the number of vertices of degree one in G'. (C) 2013 Elsevier Inc. All rights reserved.