# Construction for the Sequences ofQ-Borderenergetic Graphs

Authors: Bo Deng; Caibing Chang; Haixing Zhao; Kinkar Chandra Das
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This research intends to construct a signless Laplacian spectrum of the complement of anyk-regular graph G with order n. Through application of the join of two arbitrary graphs, a new class of Q-borderenergetic graphs is determined with proof. As indicated in the research, with a regular Q-borderenergetic graph, sequences of regular Q-borderenergetic graphs can be constructed. The procedures for such a construction are determined and demonstrated. Significantly, all the possible regular Q-borderenergetic graphs of order 7<n≤10 are determined.


---

## Body

## 1. Introduction

All graphs considered in this paper are simple, unweighted, and undirected. LetG be a graph of order n=VG, where VG is the vertex set of G. The complement of G is denoted by G¯. The complete graph of order n is denoted by Kn. Denote the average vertex degree of G by d¯. The join of two graphs H1 and H2 is the graph H1∇H2 with the vertex set VH1∪VH2 and the edge set consisting of all the edges of H1 and H2 together with the edges joining each vertex of H1 with every vertex of H2. For details on graph theory and spectral graph theory; see [1–4].LetAG and DG be the adjacency matrix and the diagonal matrix of the vertex degrees of G, respectively. Then, LG=DG−AG and QG=DG+AG are called the Laplacian matrix and the signless Laplacian matrix of G, respectively. In particular, the signless Laplacian spectra of join of two regular graphs are already determined [5].The energyEG of G is defined as the sum of the absolute value of the eigenvalues of its adjacency matrix AG [6, 7]. Let λ1≥λ2≥⋯≥λn be the eigenvalues of A. Then,(1)EG=∑i=1nλi.For additional information on graph energy and its applications in chemistry, we refer to [8–10]. The eigenvalues of the Laplacian matrix LG of graph G are denoted by ξ1≥ξ2≥⋯≥ξn=0. The Laplacian energy [11] of G is defined as(2)LEG=∑i=1nξi−d¯.The eigenvalues of the signless Laplacian matrixQ of graph G are denoted by μ1≥μ2≥⋯≥μn−1≥μn, which forms the signless Laplacian spectrum SpecQG. The signless Laplacian energy of G [12] is defined as QEG=∑i=1nμi−d¯.In 2015, Gong et al. [13] proposed the concept of borderenergetic graphs, namely graphs of order n satisfying EG=2n−1. The corresponding results on borderenergetic graphs can be seen in [14–17]. For the Laplacian energy of a graph G, Tura [18] proposed the concept of L-borderenergetic graphs, that is, a graph G of order n is L-borderenergetic if LEG=LEKn=2n−1. More results on L-borderenergetic graphs, we can refer to [18–22].Recently, Tao and Hou [23] extended this concept to the signless Laplacian energy of a graph. If a graph has the same signless Laplacian energy as the complete graph Kn, i.e., QEG=QEKn=2n−1, then it is called Q-borderenergetic. In [23, 24], several classes of Q-borderenergetic graphs are constructed.Moreover, in this paper, through using the joint of two graphs, we construct a new class ofQ-borderenergetic graphs and present a procedure to find sequences of regular Q-borderenergetic graphs. Especially, all regular Q-borderenergetic graphs of order 7<n≤10 are presented. In addition, we obtain the signless Laplacian spectrum of the complement of any k-regular graph G of order n.


## 2. Construction onQ-Borderenergetic Graphs

At first, the signless Laplacian spectrum of the complement of anyk-regular graph G with order n is given in Lemma 1. Denote the signless Laplacian matrix of G¯ by Q¯.Lemma 1.
LetG be a k-regular connected graph of order n. If μ1≥μ2≥⋯≥μn are the eigenvalues of QG, then the eigenvalues of QG¯ are as follows:(3)2n−1−μ1=2n−1−k≥n−2−μn≥n−2−μn−1≥⋯≥n−2−μ2.Proof.
Note that the signless Laplacian matrix of the complementG¯ of G is written as(4)QG¯=n−1I−DG+J−AG−I=n−2I+J−QG,where I is an identity matrix and J is the matrix with each of whose entries is equal to 1. Since G is k-regular, we have that μ1=2k with corresponding eigenvector e=1,1,…,1T. Let x2,…,xn−1,xn be the eigenvectors of QG corresponding to the eigenvalues μ2,…,μn−1,μn, respectively. Thus, we have QGxi=μixi, i=2,…,n. Since QG is symmetric, all the eigenvectors e,x2,…,xn−1,xn are orthogonal to each other. Thus, we obtain eTxi=0,i=2,…,n. As J can be presented as(5)J=eTeTeT⋮eT,it arrives at Jxi=0, i=2,…,n. Therefore,(6)QG¯xi=n−2I+J−QGxi=n−2xi+Jxi−QGxi=n−2−μixi,i=2,…,n.
Thus,n−2−μi is an eigenvalue with corresponding eigenvector xi of QG¯, where i=2,…,n. As G¯ is n−1−k-regular, 2n−1−k is an eigenvalue with corresponding eigenvector e=1,…,1T.
Using Lemma1, we obtain the signless Laplacian spectrum of the join of two special graphs in the following theorem.Theorem 1.
LetG1 be a k-regular graph on n vertices and G2 be an empty graph on n−k vertices. If 2k=μ1≥μ2≥⋯≥μn are the signless Laplacian eigenvalues of G1, then the signless Laplacian eigenvalues of G1∇G2 are(7)n−k+μ2,n−k+μ3,…,n−k+μn,nn−k−1,k,2n.Proof.
Note that the join ofG1 and G2 can also be expressed with(8)G1∇G2=G1¯∪G2¯¯.
Since2k=μ1≥μ2≥⋯≥μn and 0n−k are the signless Laplacian eigenvalues of G1 and G2, respectively, by Lemma 1, we have that the signless Laplacian spectra of G¯1 and G¯2 are as follows:(9)n−2−μn,n−2−μn−1,…,n−2−μ2,2n−1−μ1=2n−1−k,n−k−2n−k−1,2n−k−1.
Thus, the set of the signless Laplacian eigenvalues ofG¯1∪G¯2 is composed of the above two sets. Using Lemma 1, we obtain the signless Laplacian eigenvalues of G1∇G2 as follows:(10)n−k+μ2,n−k+μ3,…,n−k+μn,nn−k−1,k,2n.
Using Theorem1, from any k-regular Q-borderenergetic graph, we can construct a new class of Q-borderenergetic graphs in the following theorem.Theorem 2.
LetG be a k-regular Q-borderenergetic graph with n vertices. Then G∇K¯n−k is Q-borderenergetic.Proof.
Let2k=μ1≥μ2≥⋯≥μn be the signless Laplacian eigenvalues of G. Since G is Q-borderenergetic, then we have(11)∑i=1nμi−k=2n−2.
Letp=n−k. By Theorem 1, the Q-spectrum of G∇Kp¯ is(12)SpecQG∇Kp¯=p+μ2,p+μ3,…,p+μn,n,…,n︸n−k−1,k,2n.
Sincep=n−k, the average degree d¯ of graph G∇Kp¯ is(13)d¯=nk+2npn+p=nk+2nn−kn+n−k=n.
By the definition of signless Laplacian energy of a graph with (11), we have(14)QEG∇Kp¯=∑i=2nμi−k+n−nn−k−1+k−n+2n−n=∑i=1nμi−k−μ1−k+n−k+n=2n−2−2k−k+n−k+n=22n−k−1.
SinceVG∇Kp¯=2n−k, from the above result, we conclude that G∇Kp¯ is Q-borderenergetic.


## 3. Sequences ofQ-Borderenergetic Graphs

In this section, by using Theorem2 repeatedly, an infinite sequence of Q-borderenergetic graphs is constructed. Let G0 be any k-regular Q-borderenergetic graph with n vertices. Consider an infinite sequence H of graphs, i.e., H=G0,G1,…,Gs,… such that(15)G1=G0∇K¯n−k,G2=G1∇K¯n−k,…,Gs=Gs−1∇K¯n−s,…One can easily see that graphGss=1,2,… is of orders n+sn−k and n+s−1n−k-regular. And the signless Laplacian spectrum of Gs is given in the following lemma.Lemma 2.
LetG0 be a k-regular Q-borderenergetic graph of order n with signless Laplacian eigenvalues 2k=μ1≥μ2≥⋯≥μn−1≥μn. Then for any Gs∈Hs≥1, the signless Laplacian spectrum of Gs is the following:(16)SpecQGs=μ2+sn−k,μ3+sn−k,…,μn+sn−k,n+s−1n−k,…,n+s−1n−k︸sn−k−1,n+s−2n−k,2n+2s−1n−k.Proof.
We prove this lemma by mathematical induction ons. For s=1, by Theorem 2, (16) holds. We now assume that the result holds for s=t. Then we have(17)SpecQGt=μ2+tn−k,μ3+tn−k,…,μn+tn−k,n+t−1n−k,…,n+t−1n−k︸tn−k−1,n+t−2n−k,2n+2t−1n−k.
Now, we haveGt+1=Gt∇K¯n−k. By Theorem 1, we obtain(18)SpecQGt+1=μ2+t+1n−k,μ3+t+1n−k,…,μn+t+1n−k,n+tn−k,…,n+tn−k︸t+1n−k−1,n+t−1n−k,2n+2tn−k.
Again (16) holds for s=t+1. This completes the proof of the lemma.Theorem 3.
For anys≥1, Gs∈H is Q-borderenergetic.Proof.
Since the graphGs is n+s−1n−k-regular with order n+sn−k, by Lemma 2 and the definition of signless Laplacian energy, we have(19)QEGs=∑i=2nμi+sn−k−n−s−1n−k+sn−k−1n+s−1n−k−n−s−1n−k+sn+s−2n−k−n−s−1n−k+2n+s−1n−k−n−s−1n−k∑i=2nμi−k+sn−k+n+s−1n−k=2n−2−μ1−k+n+2s−1n−k=2n−2−k+n+2sn−k−n+k=2n+sn−k−1.
Hence,Gs is Q-borderenergetic.
In fact, for ak-regular graph G, we can check that the three kinds of energies of G are equal, i.e., QEG=LEG=EG.Lemma 4.
[20] If G is a k-regular graph, then LEG=EG.Theorem 5.
IfG is a k-regular graph of order n, then LEG=EG=QEG.Proof.
Obviously, the average degree ofG is k. The former equality holds by Lemma 4. Moreover,(20)QEG=∑i=1nμi−k=∑i=1nk+λi−k=EG.
This completes the proof of the theorem.
For ak-regular graph of order n, if G is borderenergetic, then G is Q-borderenergetic and L-borderenergetic. In [13], Gong et al. found all the borderenergetic graphs with order 7≤n≤9. Bearing in mind that there are no noncomplete borderenergetic graphs with order n<7. Furthermore, Li et al. [17] searched for the borderenergetic graphs of order 10. Thus, we can find all the regular Q or L-borderenergetic graph of order n, 7≤n≤10 (Figure 1). Denote the i-th k-regular Q-borderenergetic graph of order n by Gn,ki.Figure 1
The regularQ-borderenergetic graphs (a) G8,51, (b) G9,42, (c) G9,43, (d) G10,74, (e) G10,65, and (f) G10,66.
(a)(b)(c)(d)(e)(f)



---

*Source: 6176849-2020-07-18.xml*