The Q -generating Function for Graphs with Application
- PDF / 342,388 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 115 Downloads / 206 Views
The Q-generating Function for Graphs with Application Shu-Yu Cui1,2 · Gui-Xian Tian1 Received: 17 April 2020 / Revised: 13 August 2020 / Accepted: 2 September 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract For a simple connected graph G, the Q-generating function of the numbers Nk of semi k N edge walks of length k in G is defined by W Q (t) = ∞ k=0 k t . This paper reveals that the Q-generating function W Q (t) may be expressed in terms of the Q-polynomials of the graph G and its complement G. Using this result, we study some Q-spectral properties of graphs and compute the Q-polynomials for some graphs obtained from various graph operations, such as the complement graph of a regular graph, the join of two graphs and the (edge)corona of two graphs. As another application of the Q-generating function W Q (t), we also give a combinatorial interpretation of the Qcoronal of G, which is defined to be the sum of the entries of the matrix (λIn − Q(G))−1 . This result may be used to obtain the many alternative calculations of the Q-polynomials of the (edge)corona of two graphs. Further, we also compute the Qgenerating functions of the join of two graphs and the complete multipartite graphs. Keywords Signless Laplacian matrix · Q-polynomial · Q-spectrum · Q-generating function · Q-coronal · Semi-edge walk Mathematics Subject Classification 05C50 · 05C90
1 Introduction Throughout this paper, we consider only simple connected graphs. Let G = (V , E) be a graph with vertex set V = {v1 , v2 , . . . , vn }. Two vertices vi and v j of G are
Communicated by Xueliang Li. This work was supported by the National Natural Science Foundation of China (No. 11801521).
B
Gui-Xian Tian [email protected]; [email protected]
1
Department of Mathematics, Zhejiang Normal University, Jinhua 321004, People’s Republic of China
2
Xingzhi College, Zhejiang Normal University, Jinhua 321004, People’s Republic of China
123
S.-Y. Cui, G.-X. Tian
called adjacent, denoted by vi ∼ v j , if they are connected by an edge. The adjacency matrix A(G) of G is a square matrix of order n, whose entry ai, j is defined as follows: ai, j = 1 if vi ∼ v j , and ai, j = 0 otherwise. Let D(G) be the diagonal degree matrix of G. The matrix Q(G) = D(G) + A(G) is called the signless Laplacian matrix of G. The Q-spectrum of G is defined to S(G) = (q1 (G), q2 (G), . . . , qn (G)), where q1 (G) ≥ q2 (G) ≥ · · · ≥ qn (G) are the eigenvalues of Q(G). They also are the roots of the Q-polynomial f Q (λ) = det(λIn − Q(G)) of G. If it is clear from the context, then we use Q and qi instead of Q(G) and qi (G), respectively. Denote Qpolynomial of the complement graph G of G by f Q (λ) = det(λIn − Q(G)). For more information on the Q-spectrum and Q-polynomial, we refer the reader to [1,5–10,16] and the references therein. Let G be a simple connected graph and A(G) be its adjacency matrix. A walk (of length k) in G is an alternating sequence v1 , e1 , v2 , e2 , . . . , vk , ek , vk+1 of vertices v1 , v2 , . . . , vk+1 and
Data Loading...
