Proof of a conjecture on the number of spanning trees of line graphs and its generalization

• 作 者: Fengming Dong Weigen Yan
• 机 构: MathematicsandMathematicsEducation,NationalInstituteofEducation,NanyangTechnologicalUniversity,Singa
• 出 处: 第六届全国组合数学与图论大会
• 发表日期: 2014年11期

Let G be an arbitrary loopless connected graph.In this paper we show that t(L(Sr(G)))=Π v∈V(G) d(v)d(v)-2 Σ E(C)E(G) t(G-E)r|E(G)|-|v(G)|+1-|E|Π e∈E (d(ue)-1+d(ve)-1),where ue and ve are the two ends of edge e, t(G) is the number of spanning trees of G, L(G) is the line graph of G and for any non-negative integer r, Sr(G) is the graph obtained from G by replacing each non-bridge edge e by a path of length r+ 1 connecting the two ends of e.Thus we generalize some known results on the relation between t(L(G)) and t(G) and prove a conjecture that t(L(S1(G))) =km+s-n-1(k+2)m-n+1t(G)for any graph G of order n + s and size m + s in which s vertices are of degree 1 and the others are of degree k.