# The Least Eigenvalue of the Complement of the Square Power Graph ofG

Authors: Lubna Gul; Gohar Ali; Usama Waheed; Sumiya Nasir
Journal: Complexity
 (2021)

---

## Abstract

LetGn,m represent the family of square power graphs of order n and size m, obtained from the family of graphs Fn,k of order n and size k, with m≥k. In this paper, we discussed the least eigenvalue of graph G in the family Gn,mc. All graphs considered here are undirected, simple, connected, and not a complete Kn for positive integer n.


---

## Body

## 1. Introduction

LetG=V,E be a simple graph with vertex set VG=u1,u2,…,un and edge set EG. The adjacency matrix of a graph is defined to be the matrix BG=bij of order n, where bij=1 if ui is adjacent to uj, otherwise bij=0. As the graphs are undirected, BG is real and symmetric and the eigenvalues are also real and can be arranged as λ1G≤λ2G≤⋯≤λnG. The eigenvalues of BG are referred to as the eigenvalues of G, and one can easily find that λn is the largest absolute eigenvalue among all eigenvalues of G.A graphG is called minimizing in a certain graph class if its least eigenvalue attains the minimum among all the least eigenvalues of the graphs of that class. We will denote the least eigenvalue of a graph G by λminG and X for the corresponding least eigenvector. A graph is said to be a square power graph denoted by Gn2 of order n, if VGn2=VG and EGn2=EG∪uv:dGu,v=2,u,v∈VG, where dGu,v denotes the distance between vertices u and v in G; also, the bipartite square power graph is denoted by Gn2p,q, where p and q are the partitions of the vertex set VGn2.We limit our discussion to only connected graphs because we know that the spectrum (the set of eigenvalues of a graph) of a disconnected graph is the union of spectra of its connected components and so the least eigenvalue of a disconnected graph will be the minimum eigenvalue of its component among all the minimum eigenvalues of its components.There are many results in the literature regarding the least eigenvalue of a graph. Fan et al. [1] discussed the least eigenvalue of complement of trees. Hoffman [2] discussed the limiting point of the least eigenvalue of connected graphs. Hong and Shu [3] discussed the sharp lower bounds of the least eigenvalue of planar graphs. Javid [4, 5] discussed the minimizing graphs of the connected graphs whose complements are bicyclic (with two cycles) and explained the characterization of the minimizing graph of the connected graphs whose complement is bicyclic.Theorem 1.
(see [6]). For a graph G of order n,(1)λminG≥−n2n2,with equality iff G=K⌈n/2⌉,⌊n/2⌋.According to Powers et al. [7], if m is the size of a graph G, then(2)λminG≥−m.Theorem 2.
(see [8]). If G is a graph whose least eigenvalue is minimal among all the connected graphs, then(i)
G is either a bipartite graph, or(ii)
G is a join of two nested split graphsTheorem 3.
(see [9]). Let Kn,m denote the family of all connected bipartite graphs of order n and size m. Let G∈Kn,m be the graph such that its least eigenvalue is minimal among all the connected bipartite graphs, then G must be a double nested graph.


## 2. Main Results

We begin with some definitions. Given a graphG of order n, a vector X∈Rn is defined on G if there exists an injective function f from VG to the entries of X, simply written as Xv=fv for each v∈VG. If X is an eigenvector of BG, then it is naturally defined on VG and every entry of X corresponds to the vertex v∈VG. One can easily prove that(3)XTBX=2∑uv∈EGXuXv,and λ is an eigenvalue of G corresponding to the eigenvector X if and only if X≠0, and Nu=v∈VG:uv∈EG is called the open neighborhood of u in G:(4)λXu=∑v∈NuXv,for each vertexu∈VG.Equation (4) is called the eigen equation for the graph G. Now, for any arbitrary unit vector X∈Rn,(5)λminG≤XTBGX,and it will be equal iff X is a least eigenvector of G. Now, let Gc denote the complement of a graph G. One can easily prove that BGC=J−I−BG, where I and J denote the identity matrix and the ones matrix of the same size as BG. Now, for any vector X,(6)XTBGCX=XTJ−IX−XTBGX.A graphG is said to be a tree iff there is a path between any pair of vertices and has no cycle, and a tree is said to be a star iff there exists a vertex of degree n−1 and all other vertices have degree one. The former is called the central vertex, and the later is called the pendant vertex. If a graph G is a path of order less than or equal to 4 then λminGc=−1. If a graph G contains K1,2 as an induced subgraph, then λminG≤λminK1,2=−2. If a graph G is complete or its complement is a null graph or union of disjoint complete graph, then λminGc=−1. So, we are limiting our discussion to Gn2c−Knc, where Knc denotes all those graphs whose λmin is −1.Special tree graph denoted byGp,q is obtained from two stars Sp−1 and Sq−1 of orders p and q, respectively, by joining any two vertices of degree one from the two stars. G2p,q is a square power graph of this tree and G2p,qc is its complement graph, as shown in Figure 1; the order of G2p,qc is n=p+q, and its size is m=pq−3.Figure 1
Gn2c=G2p,qc graph with m=pq−3.Lemma 1.
Givenn≥6, for any positive integers pandq such that p≥q≥1 and p+q=n,(7)λminGn2p,qc≥λminGn2p+q2,p+q2c,with equality iff p=⌈p+q/2⌉ and q=⌊p+q/2⌋.Proof.
Forn≥6, let λmin be the least eigenvalue of Gn2p,qc and X be the corresponding least eigenvector. Let Xi denote the entries of X corresponding to the vertices of Gn2c. Now, by eigen equation, all the vertices u1,u2,u3,…,up−2 have the same values, say X1 and X2 denote the entry of X corresponding to the vertex up−1, X3 for the vertex up, and all the vertices v1,v2,v3,…,vq−2 have the same value X4. X5 represents the entry of X corresponding to the vertex vq−1, and for the vertex vq, the entry of X is X6. Now, λminGn2p,qc<−1. So, by an eigen equation,(8)λminX1=X6+X5+q−2X4,λminX2=X5+q−2X4,λminX3=q−2X4,λminX4=p−2X1+X2+X3,λminX5=p−2X1+X2,λminX6=p−2X1.
Transform (8) into a matrix equation B−λ1IX′=0, where X′=X1,X2,X3,X4,X5,X6T and the matrix B of order 6 is omitted. We get(9)fλ;p,q=detB−λI=2p+2q−pq−4−λ25p+5q−3pq−8−λ4pq−3+λ6,fλ;p,q−fλ;p−1,q+1=p−q−1λ4−3λ2+1.
Note thatλmin is a least root of fλ;p,q. In addition, f−1,6180;p,q=6.8538−17.9426p+q<0 as p+q=n≥6, which implies λmin<−1.6180.
Ifp≥q, by the above discussion, for λmin<−1.6180, we have(10)fλ;p,q−fλ;p−1,q+1<0.
In particular,fλmin;p−1,q+1<0, which implies(11)λminGn2p,qc≥λminGn2p−1,q+1c.
This complete the proof.Considering the family of square power graphsGn,m of order n and size m obtained from the family of graphs Fn,k of order n and size k with m≥k, we have the following result.Lemma 2.
LetG be a graph in Gn,mc−Knc and let X be its least eigenvector, then X contains at least two positive and two negative entries.Before we state the other results, we need some definitions.LetG be a bipartite graph with colour classes U and V such that VG=U∪V; G is said to be a double nested graph if U=U1∪U2∪⋯∪Uk and V=V1∪V2∪⋯∪Vk such that each ui∈Um is adjacent to every vertex in V−∪i=k−m+2kVi, for m∈1,2,3,…,k.Now, as we know that, from [9], if two vertices u and w belong to the same colour class and xu≥xw, then degu≥degw, where xv is the entry in eigenvector X corresponding to the vertex v.LetU=u1,u2,…,uk and V=v1,v2,…,vk be the colour classes such that xu1≥xu2≥xu3≥⋯≥xuk and xv1≥xv2≥xv3≥⋯xvk≥, where xui and xvi for i∈1,2,3,…,k are the entries of the corresponding eigenvector X of G.Lemma 3.
(see [9]). Let G be a graph with the above assumptions, then(i)
The verticesu1 and v1 are adjacent(ii)
The degree ofu1 and v1 is complete(iii)
If the vertexu is adjacent to vi, then u is adjacent to vj for j<k, and if the vertex v is adjacent to ui, then v is adjacent to uj for j<k.Observation 1.
IfG is a bipartite graph of order n and size m, then λminG goes to its lower bound by increasing the size of G.Bell et al. [9] discussed the behavior of maximum eigenvalue by increasing the number of edges and kept VG fixed. We here show the behaviour of least eigenvalue of G∈Gn,mc−Knc by fixing the number of edges at m=pq−3 and increasing the number of vertices. In Figure 2, the horizontal axes show vertices and vertical axes represent least eigenvalues.Figure 2
Relation between number of vertices and its corresponding least eigenvalue.Theorem 4.
LetG=Gn2c be a graph of order n≥6 from the family Gn,mc−Knc. Then,(12)λminGn2c≥λminGn2p+q2,p+q2c.Proof.
As we know that(13)λminGn2p,qc≥λminGn2p+q2,p+q2c,by Theorems 2 and 3, it is found that Gn2p,qc is a largest double nested graph. Let Gn2p,qc be the graph such that λminGn2p,qc is the least one among all the square power graphs and let X be the least eigenvector. Now, let Gn2 be the graph obtained from Gn2p,qc by rotating the edge ris to rit such that s≁t for i∈1,2,…,k, then λminGn2≤λminGn2p,qc and similarly if s and t belong to the same colour class such that xs≥xt, then deg (s) ≥ deg (t). So, by Lemma 2.3, it will be a double nested graph. Now, we need to show that it is the largest possible double nested graph. The size of Gn2p,qc is pq−3. So, all we need to show is the size cannot exceed pq−3. On the contrary, let m>pq−3. Then, either m=pq−2 or m=pq−1. In both cases, the connected square power graph is not possible because if we take Gn2p,qc with the size greater than pq−3, then Gn2p,q will be a disconnected graph, e.g., Gn2p,q for n=8 which is not allowed. So, this completes the proof [10].



---

*Source: 5885834-2021-09-16.xml*