Complexity of Join and Corona graphs and Chebyshev polynomials

Abstract

Boesh and Prodinger have shown how to use properties of Chebyshev polynomials to compute formulas for the number of spanning trees of some special graphs. In this paper, we extend this idea for some operations on graphs such as, Join and Corona of two graphs $ {G_1} $ and $ {G_2} $ , if $ {G_1} $ and $ {G_2} $ are one of the following graphs: (i) Path graph $ {P_n} $ , (ii) Cycle graph $ {C_n} $ , (iii) Complete graph $ {K_n} $ , (iv) Complete bipartite $ {K_{m,\,n}} $ , (v) Hypercube graph $ {Q_n} $ , (vi) Fan graph $ {F_n} $ and (vi) Wheel graph $ {W_n} $ .

Keywords

• Number of spanning trees
• Chebyshev polynomials
• Join
• Corona