# The Optimal Graph Whose Least Eigenvalue is Minimal among All Graphs via 1-2 Adjacency Matrix

Authors: Lubna Gul; Gohar Ali; Usama Waheed; Nudrat Aamir
Journal: Journal of Mathematics
 (2021)

---

## Abstract

All graphs under consideration are finite, simple, connected, and undirected. Adjacency matrix of a graphG is 0,1 matrix A=aij=0,ifvi=vjordvi,vj≥21,ifdvi,vj=1.. Here in this paper, we discussed new type of adjacency matrix known by 1-2 adjacency matrix defined as A1,2G=aij=0,ifvi=vjordvi,vj≥31,ifdvi,vj=2, from eigenvalues of the graph, we mean eigenvalues of the 1-2 adjacency matrix. Let Tnc be the set of the complement of trees of order n. In this paper, we characterized a unique graph whose least eigenvalue is minimal among all the graphs in Tnc.


---

## Body

## 1. Introduction

LetG=V,E be a simple graph with vertex set V=VG and edge set E=EG. Its order is VG, denoted by n, and its size is EG, denoted by m. The distance between two vertices u and v of a graph G is the length of a shortest path between them. The 1-2 adjacency matrix of G is defined to be the matrix A1,2G=aij of order n with aij=1 if 1≤dvi,vj≤2 and aij is zero for the rest cases. The solution of detxI−A1,2G is the eigenvalues of G. Since A1,2G is always symmetric and real, all the eigenvalues can be arranged as λ1G≤λ2G≤…≤λnG. We write λminG for the least eigenvalue of G. One can find that λnG is exactly the spectral radius of G.The least eigenvalue of any graph is nonpositive. For only disconnected graph, it is equal to zero. Otherwise, for graphs with at least one edge, it is less than or equal to−1 (by the interlacing theorem, see [1], p-19); it is equal to −1 if and only if G is a disjoint union of complete graphs or equivalently Gc is a null graph or a complete multipartite graph. If G contains K1,2 as an induced subgraph, then λminG≤λminK1,2=−2 (again by the interlacing theorem). For 1−2 adjacency matrix, λminK1,2=−1, and if a graph G containing P5 is an induced subgraph, then λminG≤1.There are many results in the literature concerning the largest eigenvalue (spectral radius) of simple graph; see, e.g., [2] or [1]. Javaid examined different families of graphs to pick optimal graph with respect to least eigenvalues via usual adjacency matrix in their respective graph classes in [3–5]. Lubna et al. examined square power graph of G for their least eigenvalue [6]. Recently, the problem of minimizing the least eigenvalue of graphs subject to one or more parameters has received more attention. Bell et al. [7, 8] discussed the least eigenvalue of connected graphs with prescribed order and size. Fan et al. [9] discussed the least eigenvalue of complement of trees. Liu et al. [10] discussed the least eigenvalue of unicyclic graphs with pendant vertices. Fan et al. [9] discussed the least eigenvalue of unicyclic graphs with given girth. Petrovic et al. [11] discussed the least eigenvalue of bicyclic graphs.In a family of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix is minimum in the set of the least eigenvalues of all the graphs. Denote byTn, Tnc the set of trees of order n and the set of the complements of trees order n, respectively. In this paper, we determine the unique minimizing graph in Tnc for n≥6, which is not the complement of the star graph, and we are limiting our discussion to the set Tnc−Knc where Knc denotes all those graphs whose λmin is −1.Theorem 1 (see [7]).
IfG is a graph whose least eigenvalue is minimal among all the connected graphs, then(i)
G is either a bipartite graph(ii)
G is a join of two nested split graphsTheorem 2 (see [12]).
LetKn,m denote the family of all connected bipartite graphs and 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 called defined on G if there exists an injective function f from VG to the entries of X; simply written Xv=fv for each v∈VG, if X is an eigenvector of A1,2G, then it is naturally defined on VG and every entry of X corresponds to the vertex v∈VG. One can easily prove that(1)XTA1,2GX=2∑du,v∈1,2XuXv,and λ is an eigenvalue of G corresponding to the eigenvector X iff X≠0 and(2)λXu=∑v∈NGuXv,for each vertexu∈VG,where NGu denotes the neighbourhood of u in the graph G. Equation (2) is called the eigen equation for the graph G. Now, for any arbitrary unit vector X∈Rn,(3)λminG≤XTA1,2GX,and it will be equal if and only if X is a least eigenvector of G. Now, let Gc denote the complement of a graph G. One can easily proof that A1,2Gc=J−I−A1,2G, where I and J denote the identity matrix and ones matrix of the same size as A1,2G. Now, for any vector X,(4)XTA1,2GcX=XTJ−IX−XTA1,2GX.A graphG is said to be a tree if and only if there is a path between any pair of vertices and has no cycle. A tree is said to be a star if and only if there exists a vertex of degree n−1 and all other vertices have degree 1. We introduce a special tree, denoted by Tp,q, which is obtained from two disjoint stars K1,pp≥1 and K1,qq≥1 by joining one pendant vertex of K1,p and one pendant vertex of K1,q. The complement of Tp,q is Gc=Tp,qc, as shown in Figure 1.Figure 1
Gc=Tp,qc graph with m=pq+p+q−2.Lemma 1.
Givenn≥6, for any positive integer p,q such that p≥q≥1 and p+q+2=n, λminTp,qc1,2≥λminTn−2/2,n−2/2c1,2, with equality if and only if p=n−2/2 and q=n−2/2.Proof.
Supposen≥6. Let λ1 be the least eigenvalue of Tp,qc and X be the corresponding least eigenvector. Let Xi denote the entries of X corresponding to the vertex vi for i=1,2,3,4,5,6. Now, by eigen equation (2), all the vertices attached at v2 and v5 have the same values given by X, say X1 and X6. Now, as λminTp,qc<−1, so by an eigen equation,(5)λ1X1=X4+X5+q−1X6,λ1X2=X5+q−1X6,λ1X3=q−1X6,λ1X4=p−1X1,λ1X5=p−1X1+X2,λ1X6=p−1X1+X2+X3.
Transform (5) into a matrix equation B−λ1IX′=0, where X′=X1,X2,X3,X4,X5,X6T and the matric B of order 6 is omitted. We get(6)fλ;p,q=detB−λI=p+q−pq−1−λ22p+2q−3pq−1−λ4p+q+pq−2+λ6,
and(7)fλ;p,q−fλ;p−1,q+1=p−q−1λ4−3λ2+1.
Note thatλ1 is a least root of fλ;p,q. In addition, f−1,6180;p,q=33.2670+0.00024593pq−11.0894p+q<0 as p+q=n−2≥4, which implies λ1<−1.6180.
Ifp≥q+2, by the above discussion, for λ1<−1.6180, we have(8)fλ;p,q−fλ;p−1,q+1<0.
In particular,fλ1;p−1,q+1<0, which implies(9)λminTp,qc≥λminTp−1,q+1c.
The result now follows.Lemma 2.
LetTc be a graph in Tnc−Knc and let X be the least eigenvector of T, then X contains at least two positive and two negative entries.Proof.
Assume on contrary thatX contains exactly one positive entry corresponding to the vertex w, i.e., Xw>0. Since T is not a star, there exists a vertex u∈NTw such that NTu∖w≠0. Considering the eigen equation (2) on the vertex u for the graph Tc, we have(10)0≤λ1TcXu=∑dv,u∈1,2Xv≤0.
This implies thatXu=0 and Xv=0 for each v∈NTcu, now as(11)λ1TcXw=∑dv,w∈1,2Xv.
Now, letv0∈NTu,w. Then, by (2) and (11),(12)1+λ1TcXv0=Xv0+∑v∈dv,v0∈1,2∖v0Xv,=∑v∈dv,v0∈1,2Xv,=Xw+∑dv,v0∈1,2∖wXv,=Xw+λ1TcXw,=1+λ1TcXw.
This impliesXv0=Xw. Since λ1Tc<1 as T is not a star, a contradiction, so our supposition is wrong and hence X contains at least two positive entries. Similarly, if we consider −X, we also get X which contains at least two negative entries. The result follows.Before we state 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∈U1 is adjacent to each and every vertex in V, and similarly, each ui∈U2 is adjacent to each and every vertex in V=V1∪V2∪…∪Vk−1 for i=1,2,3,…,k.Now, as we know from [12], if the two vertices u and w belong to the same colour class and xu≥xw, then degu≥degw.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 [12]).
Let G be a graph with the above assumptions. Then,(1)
The verticesu1 and v1 are adjacent(2)
The degree ofu1 and v1 is complete(3)
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<kObservation 1.
IfG is a bipartite of order n and size m, then λminG goes to its lower bound by increasing the size of G.
Bell [12] discussed the behavior of maximum eigenvalue by increasing the number of edges and kept VG fixed. We here show the behavior of least eigenvalue of a Tp,qc graph by fixing the number of edges at m=pq+p+q−2 and let the number of vertices be increased. In Figure 2, the horizontal axes show vertices and vertical axes represent least eigenvalues.Figure 2
The behavior of eigenvalues with respect to number of vertices.Theorem 3.
LetT be a tree of order n≥4. Then,(13)λminTc1,2≥λminTn−22,n−22c1,2.Proof.
As we know,(14)λminTp,q1,2c≥λminTn−22,n−22c1,2.
By Theorems1 and 2, it is enough to show that Tp,qc is a largest double nested graph at 1−2 distance. Let Tp,qc be the graph such that λminTp,qc is the least one among all the graphs and let X be the least eigenvector. Now, let G be the graph obtained from Tp,qc by rotating the edge ris to rit such that s≁t for i=1,2,…,k, then λminG≤λminTp,qc, and similarly, if s and t belong to the same colour class s.t xs≥xt, then deg(s)≥ deg(t), and so by Lemma 3, it will be a double nested graph. Next, we will show that it is the largest possible double nested graph at 1−2 distance. As the size Tp,qc is pq−3, so all we need to show is that the size cannot exceed pq−3. Suppose on contrary that m>pq−3, then either m=pq−2 or m=pq−1. In both cases, the connected Tp,q at 1−2 distance is not possible, which completes the proof.



---

*Source: 8016237-2021-11-17.xml*