# On the Complexity of a Class of Pyramid Graphs and Chebyshev Polynomials

Authors: S. N. Daoud
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

In mathematics, one always tries to get new structures from given ones. This also applies to the realm of graphs, where one can generate many new graphs from a given set of graphs. In this paper we define a class of pyramid graphs and derive simple formulas of the complexity, number of spanning trees, of these graphs, using linear algebra, Chebyshev polynomials, and matrix analysis techniques.


---

## Body

## 1. Introduction

In this work we deal with simple and finite undirected graphsG=(V,E), whereVis the vertex set andEis the edge set. For a graphG, a spanning tree inGis a tree which has the same vertex set asG. The number of spanning trees ofG, also known as the complexity of the graph, is denoted byτ(G); this quantity is a well-studied quantity for long time. A classical result of Kirchhoff [1] can be used to determine the number of spanning trees for a graphG. If V={v1,v2,…,vn}, then the Kirchhoff matrixHis defined asn×ncharacteristic matrixH=D-A, whereDis the diagonal matrix of the degrees ofGandAis the adjacency matrix ofG,H=[aij]defined as follows:(i)
aij=-1,whenviandvjare adjacent andi≠j;(ii)
aijequals the degree of vertexviifi=j;(iii)
aij=0otherwise. All of cofactors ofHare equal toτ(G). There are other methods for calculatingτ(G). Letμ1≥μ1≥⋯≥μpdenote the eigenvalues ofHmatrix of appoint graph. It is easily shown thatμp=0. Furthermore, Kelmans and Chelnokov [2] have shown that,τ(G)=(1/p)∏k=1p-1μk. The formula for the number of spanning trees in ad-regular graphGcan be expressed asτ(G)=(1/p)∏k=1p-1(d-λk), whereλ0=d,λ1,λ2,…,λp-1are the eigenvalues of the corresponding adjacency matrix of the graph. However, for a few special families of graphs there exist simple formulas that make it much easier to calculate and determine the number of corresponding spanning trees especially when these numbers are very large. One of the first such result is due to Cayley [3] who showed that complete graph onnvertices,Kn, hasnn-2spanning trees; that is, he showed thatτ(Kn)=nn-2,n≥2. Another result,τ(Kp,q)=pq-1qp-1,p,q≥1, whereKp,qis the complete bipartite graph with bipartite sets containingpandqvertices, respectively. It is well known, as in, for example, [4, 5]. Another result is due to Sedláček [6] who derived a formula for the wheel onn+1vertices,Wn+1; he showed thatτ(Wn+1)=((3+5)/2)n+((3-5)/2)n-2, forn≥3. Sedláček [7] also later derived a formula for the number of spanning trees in a Mobius ladder,Mn,τ(Mn)=(n/2)[(2+3)n+(2-3)n+2]forn≥2. Another class of graphs for which an explicit formula has been derived is based on a prism graph. See Boesch, et al. [8, 9].Now, we introduce the following lemma.Lemma 1 (see [10]).
Considerτ(G)=(1/n2)det(nI-D-+A-), whereA-andD-are the adjacency and degree matrices ofG-, the complement ofG, respectively, andIis then×nunit matrix.The advantage of this formula is to expressτ(G)directly as a determinant rather than in terms of cofactors as in Kirchhoff theorem or eigenvalues as in Kelmans and Chelnokov formula.


## 2. Chebyshev Polynomial

In this section we introduce some relations concerning Chebyshev polynomials of the first and second kind which we use in our computations.We begin with their definitions; see Zhang et al. [11].LetAn(x)ben×nmatrix such that
(1)An(x)=(2x-10⋯0-12x-1⋱⋮0⋱⋱⋱0⋮⋱⋱⋱-10⋯0-12x).
Further, we recall that the Chebyshev polynomials of the first kind are defined by
(2)Tn(x)=cos(narccosx).The Chebyshev polynomials of the second kind are defined by(3)Un-1(x)=1nddxTn(x)=sin(narccosx)sin(arccosx).It is easily verified that(4)Un(x)-2xUn-1(x)+Un-2(x)=0.It can then be shown from this recursion that by expanding detAn(x)one gets
(5)Un(x)=det(An(x)),n≥1.Furthermore by using standard methods for solving the recursion (4), one obtains the explicit formula
(6)Un(x)=12x2-1[(x+x2-1)n+1-(x-x2-1)n+1],hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhn≥1,
where the identity is true for all complexx(except atx=±1, where the function can be taken as the limit).The definition ofUn(x)easily yields its zeros and it can therefore be verified that
(7)Un-1(x)=2n-1∏j=1n-1(x-cosjπn).One further notes that(8)Un-1(-x)=(-1)n-1Un-1(x).These two results yield another formula forUn(x):
(9)Un-12(x)=4n-1∏j=1n-1(x2-cos2jπn).Finally, a simple manipulation of the above formula yields the following formula (10), which is extremely useful to us latter:
(10)Un-12(x+24)=∏j=1n-1(x-2cos2jπn).Furthermore, one can show that(11)Un-12(x)=12(1-x2)[1-T2n]=12(1-x2)[1-Tn(2x2-1)].And(12)Tn(x)=12[(x+x2-1)n+(x-x2-1)n].
Now we introduce the following important two lemmas.Lemma 2 (see [10]).
LetBn(x)ben×ncirculant matrix such that
(13)Bn(x)=(x01⋯100⋱⋱⋱⋱11⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱11⋱⋱⋱⋱001⋯10x).
Then forn≥3,x≥4, one has
(14)det(Bn(x))=2(x+n-3)x-3[Tn(x-12)-1].Lemma 3 (see [12]).
IfA∈Fn×n,B∈Fn×m,C∈Fm×n, andD∈Fm×m, assuming thatAandDare nonsingular matrices, then
(15)det(ABCD)=det(A-BD-1C)detD=detAdet(D-CA-1B).
This lemma gives a sort of symmetry for some matrices which facilitates one’s calculations of the complexities of some special graphs.


## 3. Main Results

Definition 4.
The pyramid graphPn(m)is the graph formed from the wheel graphWm+1with vertices{v0,v1,v2,…,vm}andmsets of vertices, say,{u11,u21,…,un1},{u12,u22,…,un2},…,{u1m,u2m,…,unm}, such that for alli=1,2,…,nthe vertexuijis adjacent tovjandvj+1, wherej=1,2,…,m-1, anduimis adjacent tov1andvm.See Figures 1(a) and 1(b).(a) The triangular pyramid graphP3(3). (b) The square pyramid graphP4(4).
(a)
(b)Theorem 5.
Forn≥0,
(16)τ(Pn(3))=23n-2×(3n+8)2.Proof.
Applying Lemma1, we have(17)τ(Pn(3))=1(3n+4)2det((3n+4)I-D-+A-)=1(3n+4)2det(40001⋯⋯⋯⋯⋯⋯⋯102(n+2)000⋯01⋯10⋯0002(n+2)00⋯00⋯01⋯10002(n+2)1⋯10⋯00⋯0100131⋯⋯⋯⋯⋯⋯1⋮⋮⋮⋮1⋱⋱⋱⋱⋱⋱⋱⋮⋮001⋮⋱⋱⋱⋱⋱⋱⋱⋮⋮100⋮⋱⋱⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋱⋱⋮⋮100⋮⋱⋱⋱⋱⋱⋱⋱⋮⋮010⋮⋱⋱⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋱⋱110101⋯⋯⋯⋯⋯⋯13).Letj=(1⋯1)be the1×nmatrix with all one andJnthen×nmatrix with all one. Seta=2n+4andb=3n+4. Then we have(18)τ(Pn(3))=1b2det(4000jjj00j00aI300j0j00jt00jtjtjt002I3n+J3njt0jt0)=1b2det(b000jjjb0j0baI300jbj00bjt00jtbjtjt002I3n+J3nbjt0jt0)=1bdet(1000jjj10j01aI300j1j001jt00jt1jtjt002I3n+J3n1jt0jt0)=1bdet(1000jjj0-j0-j0aI3-j-j000-j-j000jt0jt002I3n00jt0)=1bdet(-j0-jaI3-j-j00-j-j00jtjt002I3n0jt0).
Using Lemma 3 yields
(19)τ(Pn(3))=1bdet(aI3BC2I3n)=1bdet(aI3-B·12I3nC)·23n=1b23n-3·2bdet(1nn12an1n2a)=23n-2det(1nn02a-n0002a-n)=23n-2(2a-n)2=23n-2(3n+8)2.Theorem 6.
Forn≥0,
(20)τ(Pn(4))=24n×(n+3)2×(2n+5).Proof.
Applying Lemma1, we have(21)τ(Pn(4))=1(4n+5)2det((4n+5)I-D-+A-)=1(4n+5)2×det(500001⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯102(n+2)0100⋯01⋯11⋯10⋯0002(n+2)010⋯00⋯01⋯11⋯10102(n+2)01⋯10⋯00⋯01⋯100102(n+2)1⋯11⋯10⋯00⋯01001131⋯⋯⋯⋯⋯⋯⋯⋯⋯1⋮⋮⋮⋮⋮1⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮0011⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮1001⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮1001⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮1100⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮1100⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮0110⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱1101101⋯⋯⋯⋯⋯⋯⋯⋯⋯13) Letj=(1⋯1)be the1×nmatrix with all one andJnthen×nmatrix with all one. Seta=2n+4andb=4n+5. Then we have
(22)τ(Pn(3))=1b2×det(50000jjjj0a0100jj000a0100jj010a0j00j0010ajj00jt00jtjtjtjt00jtjtjtjt002I4n+J4njt0jtjt0)12=1b2×det(b0000jjjjba0100jj0b0a0100jjb10a0j00jb010ajj00bjt00jtjtbjtjt00jtbjtjtjt002I4n+J4nbjt0jtjt0)=1b2×det(10000jjjj1a0100jj010a0100jj110a0j00j1010ajj001jt00jtjt1jtjt00jt1jtjtjt002I4n+J4n1jt0jtjt0)=1b×det(10000jjjj0a010-j00-j00a01-j-j00010a00-j-j00010a00-j-j000jtjt0jt00jt2I4n0jtjt0000jtjt0)=1b×det(a010-j00-j0a01-j-j0010a00-j-j0011a00-j-j00jtjtjt00jt2I4njtjt000jtjt0).
Using Lemma 3 yields
(23)τ(Pn(4))=1bdet(ABB2I4n)=1bdet(A-B·12I4nC)·24n=1b24n·2-4×det(2an2(n+1)nn2an2(n+1)2(n+1)n2ann2(n+1)n2a)=1b24n-4×det(2a+4n+2n2(n+1)n2a+4n+22an2(n+1)2a+4n+2n2an2a+4n+22(n+1)n2a)=1b24n·2-4·2b×det(1n2(n+1)n12an2(n+1)1n2an12(n+1)n2a)=24n-3×det(1n2nn02a-n-n-2n+2002a-2n-200n+2-n-22a-n)=24n-3·8(a+1)(a-n-1)2=24n(2n+5)(n+3)2.Theorem 7.
Forn≥0,m≥3,
(24)τ(Pn(m))=2mn-m[(n+3+2n+5)m+(n+3-2n+5)m-2(n+2)m].Proof.
Applying Lemma1, we have
(25)τ(Pn(m))=1(mn+m+1)2det((mn+m+1)I-D-+A-)=1(mn+m+1)2×det((m+1)00⋯⋯⋯⋯⋯01⋯⋯⋯⋯⋯02(n+2)01⋯⋯⋯100⋯01⋯1⋮02(n+2)01⋱⋱⋱10⋯00⋯0⋮10⋱⋱⋱⋱⋱⋮1⋯10⋯0⋮⋮⋱⋱⋱⋱⋱⋱⋮1⋯11⋯1⋮⋮⋱⋱⋱⋱⋱⋱⋮⋯⋯⋯⋯⋯⋯⋮⋮⋱⋱⋱⋱⋱⋱1⋯⋯⋯⋯⋯⋯⋮1⋮⋱⋱⋱⋱⋱01⋯1⋯⋯⋯001⋯⋯⋯102(n+2)1⋯1⋯⋯⋯10011⋮⋮1131⋯⋯⋯⋯⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮0011⋮⋮11⋮⋱⋱⋱⋱⋱⋮1001⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮1001⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮⋮100⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮⋮100⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮⋮⋮10⋮⋮1⋮⋮⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮⋮⋮10⋮⋮1⋮⋮⋱⋱⋱⋱⋱⋮⋮⋮⋮1⋮⋮01⋮⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮⋮⋮⋮1⋮⋮01⋮⋱⋱⋱⋱⋱⋮1⋮⋮⋮⋮⋮00⋮⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱⋮1⋮⋮⋮⋮⋮00⋮⋱⋱⋱⋱⋱⋮0111⋮⋮10⋮⋱⋱⋱⋱⋱⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋱⋱⋱⋱⋱10111⋯⋯101⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11⋯1⋯⋯⋯⋯⋯⋯1⋯10⋯01⋯11⋯1⋯⋯⋯⋯⋯⋯1⋯10⋯01⋯1⋯⋯⋯⋯⋯⋯⋮⋮⋮0⋯00⋯01⋯1⋯⋯⋯⋮⋮⋮⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋮⋮⋮⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1⋯10⋯00⋯01⋯1⋯⋯⋯⋯⋯⋯1⋯10⋯00⋯0⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋮⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱⋱1⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯13)
Letj=(1⋯1)be the1×nmatrix with all one andJnthen×nmatrix with all one. Seta=2n+4andb=mn+m+1. Then we have (26)τ(Pn(m))=1b2det(m+10⋯⋯⋯⋯0j⋯⋯⋯⋯j0a01⋯100j⋯⋯j0⋮0a01⋯100j⋱⋱j⋮10⋱⋱⋱⋮j0⋱⋱⋱j⋮⋮⋱⋱⋱⋱1⋮⋱⋱⋱⋱⋮⋮1⋱⋱⋱⋱0⋮⋱⋱00j001⋯10aj⋯⋯j00jt00jt⋯jtjtjtjt00⋱⋱jt⋮⋮jt⋱⋱⋱⋮2Imn+Jmn⋮⋮⋱⋱⋱0jt⋮jt⋱⋱⋱00jt0jt⋯⋯jt0)=1b2det(b0⋯⋯⋯⋯0j⋯⋯⋯⋯jba01⋯100j⋯⋯j0⋮0a01⋯100j⋱⋱j⋮10⋱⋱⋱⋮j0⋱⋱⋱j⋮⋮⋱⋱⋱⋱1⋮⋱⋱⋱⋱⋮⋮1⋱⋱⋱⋱0⋮⋱⋱⋱⋱jb01⋯10aj⋯⋯j00bjt00jt⋯jtjtbjtjt00⋱⋱jt⋮⋮jt⋱⋱⋱⋮2Imn+Jmn⋮⋮⋱⋱⋱0jt⋮jt⋱⋱⋱00bjt0jt⋯⋯jt0)=1bdet(10⋯⋯⋯⋯0j⋯⋯⋯⋯j1a01⋯100j⋯⋯j0⋮0a01⋯100j⋱⋱j⋮10⋱⋱⋱⋮j0⋱⋱⋱j⋮⋮⋱⋱⋱⋱1⋮⋱⋱⋱⋱⋮⋮1⋱⋱⋱⋱0⋮⋱⋱⋱⋱j101⋯10aj⋯⋯j001jt00jt⋯jtjt1jtjt00⋱⋱jt⋮⋮jt⋱⋱⋱⋮2Imn+Jmn⋮⋮⋱⋱⋱0jt⋮jt⋱⋱⋱001jt0jt⋯⋯jt0)=1bdet(10⋯⋯⋯⋯0j⋯⋯⋯⋯j0a01⋯10-j0⋯⋯0-j⋮0a01⋯1-j-j0⋱⋱0⋮10⋱⋱⋱⋮0-j⋱⋱⋱0⋮⋮⋱⋱⋱⋱1⋮⋱⋱⋱⋱⋮⋮1⋱⋱⋱⋱0⋮⋱⋱⋱⋱0001⋯10a0⋯⋯0-j-j000jt⋯jtjt0jt00⋱⋱jt⋮⋮jt⋱⋱⋱⋮2Imn⋮⋮⋱⋱⋱⋱jt⋮jt⋱⋱⋱⋱000jt⋯⋯jt0)=1bdet(a01⋯10-j0⋯⋯0-j0a01⋯1-j-j0⋱⋱010⋱⋱⋱⋮0-j⋱⋱⋱0⋮⋱⋱⋱⋱1⋮⋱⋱⋱⋱⋮1⋱⋱⋱⋱0⋮⋱⋱⋱⋱001⋯10a0⋯⋯0-j-j00jt⋯jtjtjt00⋱⋱jt⋮jt⋱⋱⋱⋮2Imn⋮⋱⋱⋱0jtjt⋱⋱⋱000jt⋯⋯jt0).Using Lemma 3 yields(27)τ(Pn(m))=1bdet(ABB2Imn)=1bdet(A-B·12ImnC)·2mn=1b2mn·2-mdet(2an2(n+1)⋯2(n+1)nn2an2(n+1)⋯2(n+1)2(n+1)n⋱⋱⋱⋮⋮⋱⋱⋱⋱2(n+1)2(n+1)⋱⋱⋱⋱nn2(n+1)⋯2(n+1)n2a).By straightforward induction using properties of determinants, we have(28)τ(Pn(m))=1b2mn-m·2a+n(m-2)+2(m-3)mn+2m+2×det(2a-n0(n+2)⋯(n+2)002a-n0(n+2)⋯(n+2)(n+2)0⋱⋱⋱⋮⋮⋱⋱⋱⋱(n+2)(n+2)⋱⋱⋱⋱00(n+2)⋯(n+2)02a-n)=1b2mn-m·2bmn+2m+2×det(2a-n0(n+2)⋯(n+2)002a-n0(n+2)⋯(n+2)(n+2)0⋱⋱⋱⋮⋮⋱⋱⋱⋱(n+2)(n+2)⋱⋱⋱⋱00(n+2)⋯(n+2)02a-n)=2mn-m+1·(n+2)mmn+2m+2×det(2a-nn+201⋯1002a-nn+20⋱⋱110⋱⋱⋱⋮⋮⋱⋱⋱⋱11⋱⋱⋱⋱001⋯102a-nn+2).Using Lemma 2 yields
(29)τ(Pn(m))=2mn-m+1·(n+2)mmn+2m+2·2((2a-n)/(n+2)+m-3)(2a-n)/(n+2)-3×[Tm((2a-n)/(n+2)-12)-1]=2mn-m+1·(n+2)mmn+2m+2·(mn+2m+2)×[Tm(2a-2n-22(n+2))-1]=2mn-m+1·(n+2)m[Tm(n+3n+2)-1].
Using (12) yields
(30)τ(Pn(m))=2mn-m[(n+3+2n+5)m+(n+3-2n+5)m-2(n+2)m].


## 4. Conclusion

The number of spanning treesτ(G)in graphs (networks) is an important invariant. The evaluation of this number is not only interesting from a mathematical (computational) perspective, but also is an important measure of reliability of a network and designing electrical circuits. Some computationally hard problems such as the travelling salesman problem can be solved approximately by using spanning trees. Due to the high dependence of the network design and reliability on the graph theory we introduced the above important theorems and lemmas and their proofs.



---

*Source: 820549-2013-12-04.xml*