Unifying adjacency, Laplacian, and signless Laplacian theories

Aniruddha Samantaa, Deepshikhab, Kinkar Chandra Dasc,∗

aTheoretical Statistics and Mathematics Unit, Indian Statistical Institute,
Kolkata-700108, India
E-mail<EMAIL_ADDRESS>

bDepartment of Mathematics, Shyampur Siddheswari Mahavidyalaya, University of
Calcutta,
West Bengal 711312, India
E-mail<EMAIL_ADDRESS>

cDepartment of Mathematics, Sungkyunkwan University,
Suwon 16419, Republic of Korea
E-mail<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a simple graph with associated diagonal matrix of vertex degrees
$D(G)$, adjacency matrix $A(G)$, Laplacian matrix $L(G)$ and signless
Laplacian matrix $Q(G)$. Recently, Nikiforov proposed the family of matrices
$A_{\alpha}(G)$ defined for any real $\alpha\in[0,1]$ as
$A_{\alpha}(G):=\alpha\,D(G)+(1-\alpha)\,A(G)$, and also mentioned that the
matrices $A_{\alpha}(G)$ can underpin a unified theory of $A(G)$ and $Q(G)$.
Inspired from the above definition, we introduce the $B_{\alpha}$-matrix of
$G$, $B_{\alpha}(G):=\alpha A(G)+(1-\alpha)L(G)$ for $\alpha\in[0,1]$. Note
that
$L(G)=B_{0}(G),D(G)=2B_{\frac{1}{2}}(G),Q(G)=3B_{\frac{2}{3}}(G),A(G)=B_{1}(G)$.
In this article, we study several spectral properties of $B_{\alpha}$-matrices
to unify the theories of adjacency, Laplacian, and signless Laplacian matrices
of graphs. In particular, we prove that each eigenvalue of $B_{\alpha}(G)$ is
continuous on $\alpha$. Using this, we characterize positive semidefinite
$B_{\alpha}$-matrices in terms of $\alpha$. As a consequence, we provide an
upper bound of the independence number of $G$. Besides, we establish some
bounds for the largest and the smallest eigenvalues of $B_{\alpha}(G)$. As a
result, we obtain a bound for the chromatic number of $G$ and deduce several
known results. In addition, we present a Sachs-type result for the
characteristic polynomial of a $B_{\alpha}$-matrix.

MSC: 05C50, 05C22, 05C35.
Keywords: Adjacency Matrix, Laplacian Matrix, Signless Laplacian Matrix,
Convex Combination, $B_{\alpha}$-matrix, $A_{\alpha}$-matrix, Chromatic
number, Independence number.

##  1 Introduction

Throughout this article, we consider $G$ to be a simple undirected graph with
vertex set $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and edge set $E(G)$. The
adjacency matrix of $G$ is a symmetric $n\times n$ matrix $A(G)$ whose
$(i,j)$-th entry is $1$ if $v_{i}$ and $v_{j}$ are adjacent, $0$ otherwise.
The degree matrix of $G$ is a diagonal matrix $D(G)$ whose $i^{th}$ diagonal
entry is the degree of the vertex $v_{i}$. The Laplacian and the signless
Laplacian matrix of $G$ are the matrices, $L(G):=D(G)-A(G)$ and
$Q(G):=D(G)+A(G)$, respectively. If graph $G$ is clear from the context, we
simply write $A,L,$ and $D$ instead of $A(G),L(G)$, and $D(G)$, respectively.
Adjacency, Laplacian, and signless Laplacian matrices are some of the matrices
associated with a graph which are widely studied in the literature [9, 13, 28,
17, 12, 6, 8, 10, 11]. It can be seen that many of the spectral properties of
such matrices are quite different from each other. We will thus analyze the
spectral properties of the convex combinations of $A(G)$ and $L(G)$ in order
to understand how uniformly the spectral behavior transforms from one matrix
to another.

######  Definition 1.1.

For $\alpha\in[0,1]$ the $B_{\alpha}$-matrix of $G$ is the convex linear
combination $B_{\alpha}(G):=\alpha A(G)+(1-\alpha)L(G)$ (or simply
$B_{\alpha}=\alpha A+(1-\alpha)L$, if $G$ is clear from the context).

######  Remark 1.1.

Note that
$L(G)=B_{0}(G),\,D(G)=2B_{\frac{1}{2}}(G),\,Q(G)=3B_{\frac{2}{3}}(G),\,A(G)=B_{1}(G)$.

It is clear that the spectral properties of $B_{1/2}(G)$ and $B_{2/3}(G)$ are
equivalent to the spectral properties of $D(G)$ and $Q(G)$, respectively. In
fact, $A(G),L(G),Q(G),$ and $D(G)$ can be considered as the
$B_{\alpha}$-matrix of $G$ up to proportionality. Therefore, on the one hand,
the spectral properties of $B_{\alpha}(G)$ may reveal the common connection
among the spectral properties of all such well-known matrices. On the other
hand, $B_{\alpha}(G)$ may analyze the structural and combinatorial properties
of the graph $G$ in a better way.

Recently, Nikiforov [24] introduced a family of matrices, known as
$A_{\alpha}$-matrix, which is a convex combination of $A(G)$ and $D(G)$. The
theory of $A_{\alpha}$-matrices merges the theories of the adjacency matrix
and signless Laplacian matrix of graphs. Later on, much work has been done on
these matrices. We have results on the spectral radius ([1, 5, 14, 22]), the
second largest eigenvalue [4], the $k$-th largest eigenvalue [22], the least
eigenvalue ([21, 19]), the multiplicity of the eigenvalues ([3, 26]), positive
semidefiniteness [25], the characteristic polynomial [23], spectral
determination of graphs [20], etc. Motivated by Nikiforov’s work, we consider
$B_{\alpha}$-matrices and study their spectral properties. However, unlike
$A_{\alpha}$-matrices, $B_{\alpha}$-matrices are not always non-negative, but
they obey Perron-Frobenius type results. In this article, we develop the
theory of $B_{\alpha}$-matrices to unify the theory of adjacency matrix,
Laplacian matrix, and signless Laplacian matrix.

The paper is organized as follows. In Section 2, we list some previously known
results. Section 3 discusses the positive semidefiniteness of
$B_{\alpha}$-matrices. As a consequence, we obtain an upper bound for the
independence number. Then we present some bounds of eigenvalues of
$B_{\alpha}(G)$ in terms of maximum degree and minimum degree, chromatic
number, etc., in Section 4. Besides, we obtain a lower bound for chromatic
number and derive several known results as consequences. Finally, we study the
determinant and a Sachs-type result for the characteristic polynomial of
$B_{\alpha}(G)$ in Section 5.

##  2 Preliminaries

Let $G$ be a simple graph with vertex set $V(G)=\\{v_{1},v_{2},\dots,v_{n}\\}$
and edge set $E(G)$. If two vertices $v_{i}$ and $v_{j}$ are adjacent, we
write $v_{i}\sim v_{j}$, and $v_{i}v_{j}$ denotes the edge between them. The
degree of a vertex $v_{i}$ is the number of edges adjacent to $v_{i}$ and is
denoted by $d_{G}(v_{i})$ or simply $d(v_{i})$ or $d_{i}$. The minimum degree
and the maximum degree of graph $G$ are denoted by $\delta(G)$ (or simply
$\delta$) and $\Delta(G)$ (or simply $\Delta$), respectively. The complement
of a graph $G$ is the graph $\overline{G}$ with vertex set $V(G)$ and two
vertices in $\overline{G}$ are adjacent if and only if they are non-adjacent
in $G$. The $0-1$ incidence matrix of a graph $G$ with $n$ vertices
$\\{v_{1},v_{2},\dots,v_{n}\\}$ and $m$ edges $\\{e_{1},e_{2},\dots,e_{m}\\}$
is an $n\times m$ matrix $M$ whose $(i,j)$-th entry is $1$ if the vertex
$v_{i}$ is incident on the edge $e_{j}$ and $0$ otherwise.

The line graph of a graph $G$ is the graph $G_{\ell}$ with vertex set $E(G)$
and two vertices $e_{i}$ and $e_{j}$ in $G_{\ell}$ are adjacent if the edges
$e_{i}$ and $e_{j}$ have a common vertex in the graph $G$. The identity matrix
of order $n$ is denoted by $I_{n}$ (or simply $I$). An $a\times b$ matrix
whose entries are all ones is denoted by $J_{a,b}$ (or simply $J$ when the
order is clearly understood). The transpose of a matrix $M$ is denoted by
$M^{t}$.

######  Lemma 2.1.

[2, Lemma 6.16] Let $G$ be a graph with line graph $G_{\ell}$. If $M$ is the
$0-1$ incidence matrix of $G$, then $M^{t}M=A(G_{\ell})+2I$. Moreover, if $G$
is $k$-regular, then $MM^{t}=A(G)+kI$.

Since the eigenvalues of any $n\times n$ symmetric matrix $S$ are real, we
denote and ordered the eigenvalues of $S$ as follows:

$\lambda_{max}(S)=\lambda_{1}(S)\geq\lambda_{2}(S)\geq\cdots\geq\lambda_{n}(S)=\lambda_{min}(S).$
(1)

For a graph $G$, sometimes we denote and arrange the eigenvalues of
$A(G),\,L(G)$ and $Q(G)$ as
$\rho_{1}(G)\geq\rho_{2}(G)\geq\cdots\geq\rho_{n}(G)$,
$\mu_{1}(G)\geq\mu_{2}(G)\geq\cdots\geq\mu_{n}(G)$ and $q_{1}(G)\geq
q_{2}(G)\geq\cdots\geq q_{n}(G)$, respectively. Next, we present the well
known Weyl Theorem.

######  Theorem 2.1.

[16, Theorem 4.3.1] If $S_{1}$ and $S_{2}$ are two Hermitian matrices of order
$n$ and their eigenvalues are ordered as in (1). Then

$\lambda_{n+1-i}(S_{1}+S_{2})\leq\lambda_{n+1-i-j}(S_{1})+\lambda_{j+1}(S_{2}),~{}~{}~{}i=1,2,\dots,n;~{}~{}j=0,1,\dots,n-i.$

######  Corollary 2.1.

If $S_{1}$ and $S_{2}$ are two Hermitian matrices of order $n$ and their
eigenvalues are ordered as in (1). Then

$\lambda_{n}(S_{1})+\lambda_{1}(S_{2})\leq\lambda_{1}(S_{1}+S_{2})\leq\lambda_{1}(S_{1})+\lambda_{1}(S_{2}).$

Let us recall the following upper bound of the largest eigenvalue of a
Laplacian matrix.

######  Theorem 2.2.

[7] Let $G$ be a graph with the largest Laplacian eigenvalue $\mu_{1}(G)$.
Then

$\mu_{1}(G)\leq\max_{v_{i}v_{j}\in E(G)}\,(d_{i}+d_{j}).$

Let $S=\left(\begin{array}[]{cc}S_{11}&S_{12}\\\
S_{21}&S_{22}\end{array}\right)$ be a $2\times 2$ block matrix, where $S_{11}$
and $S_{22}$ are square matrices. If $S_{11}$ is nonsingular, then the Schur
complement of $S_{11}$ in $S$ is defined to be the following matrix

$S_{22}-S_{21}S_{11}^{-1}S_{12}.$ (2)

Similarly, if $S_{22}$ is nonsingular, then the Schur complement of $S_{22}$
in $S$ is $S_{11}-S_{12}S_{22}^{-1}S_{21}$. Let us recall the Schur complement
formula for the determinant.

######  Theorem 2.3.

[2] Let $S=\left(\begin{array}[]{cc}S_{11}&S_{12}\\\
S_{21}&S_{22}\end{array}\right)$ be a $2\times 2$ block matrix, where $S_{11}$
and $S_{22}$ are square matrices and $S_{11}$ is nonsingular. Then

$\det S=(\det S_{11})\,\det(S_{22}-S_{21}S_{11}^{-1}S_{12}).$

A matrix is irreducible if it is not similar via a permutation to a block
upper triangular matrix (that has more than one block of positive size). Note
that the adjacency matrix of a connected graph is always irreducible. Let
$S=(s_{ij})_{n\times m}$ be a matrix, then we denote $|S|:=(|s_{ij}|)_{n\times
m}$.

######  Theorem 2.4.

[16, Theorem 6.2.24] A square matrix $S$ of order $n$ is irreducible if and
only if $(I+|S|)^{n-1}>0$, entry-wise.

######  Theorem 2.5.

[16, Corollary 6.2.27] Let $S$ be an irreducibly diagonally dominant matrix of
order $n$. If $S$ is Hermitian and every main diagonal entry is positive, then
$S$ is positive definite.

##  3 Positive semidefiniteness of $B_{\alpha}(G)$

Let $G$ be a graph with $B_{\alpha}$-matrix $B_{\alpha}(G):=\alpha
A(G)+(1-\alpha)L(G)$. In this section we determine the values of $\alpha$ for
which the matrix $B_{\alpha}(G)$ is positive semidefinite. As a consequence,
we give an upper bound of the independence number. Results obtained in this
section will be useful in the later sections.

For simplicity, we use the notation $B_{\alpha}$, $~{}A,~{}L$, and $D$ instead
of $B_{\alpha}(G),~{}A(G),~{}L(G)$, and $D(G)$, respectively, when $G$ is
clear from the context. Some equivalent forms of $B_{\alpha}$ in terms of $A$,
$L$, and $D$ are as follows:

$\displaystyle B_{\alpha}$ $\displaystyle=\alpha A+(1-\alpha)L$
$\displaystyle=(2\alpha-1)A+(1-\alpha)D$ $\displaystyle=(1-2\alpha)L+\alpha
D.$

Given two real matrices $S=(s_{ij})_{m\times n}$ and $M=(m_{ij})_{m\times n}$,
we use the notation $S\geq M$ if and only if $s_{ij}\geq m_{ij}$ for all
$i,j$. For any connected graph $G$ with $n$ vertices and
$\alpha\,(\neq\frac{1}{2})\in[0,1]$, we have

$\displaystyle(I+|B_{\alpha}|)^{n-1}$
$\displaystyle=(I+|(2\alpha-1)A+(1-\alpha)D|)^{n-1}$
$\displaystyle=(I+|2\alpha-1|A+(1-\alpha)D)^{n-1}$ $\displaystyle\geq
I+|2\alpha-1|A+\cdots+|2\alpha-1|^{n-1}A^{n-1}.$ (3)

Since $G$ is connected, any two vertices $v_{i}$ and $v_{j}$ are joined by a
path with length $k\leq n-1$. Therefore $(i,j)$-th entry of $A^{k}$, which
counts the number of walks of length $k$ connecting $v_{i}$ and $v_{j}$, is
positive. Hence, from (3), $(I+|B_{\alpha}|)^{n-1}\geq
I+|2\alpha-1|A+\cdots+|2\alpha-1|^{n-1}A^{n-1}>0.$ Thus, by Theorem 2.4,
$B_{\alpha}$ is irreducible for $\alpha\,(\neq\frac{1}{2})\in[0,1]$.

We begin the section with the following basic property of $B_{\alpha}(G)$.

######  Proposition 3.1.

For any $\alpha\in[0,1]$, eigenvalues of $B_{\alpha}(G)$ are real numbers.

###### Proof.

Since $A(G)$ and $L(G)$ are symmetric matrices, so $B_{\alpha}(G)=\alpha
A(G)+(1-\alpha)L(G)$ is also a symmetric matrix. Hence, all the eigenvalues of
$B_{\alpha}$ are real numbers for any $\alpha\in[0,1]$. ∎

For a graph $G$, let
$\lambda_{1}(B_{\alpha})\geq\cdots\geq\lambda_{n}(B_{\alpha})$ be the
eigenvalues of $B_{\alpha}(G)$. In the following theorem, we prove that
$\lambda_{k}(B_{\alpha})$ is uniformly continuous for $\alpha\in[0,1]$.

######  Theorem 3.1.

Let $B_{\alpha}$ be the $B_{\alpha}$-matrix of a graph $G$ with $n$ vertices.
Then, for $k\in\\{1,2,\ldots,n\\}$, the mapping
$f_{G}:[0,1]\rightarrow\mathbb{R}$ defined as
$f_{G}(\alpha)=\lambda_{k}(B_{\alpha})$ is a uniformly continuous function.

###### Proof.

Let $L$ and $D$ be the Laplacian and the degree matrix of $G$, respectively.
Then, for any $\alpha,\beta\in[0,1]$, we have
$B_{\alpha}-B_{\beta}=2(\beta-\alpha)L+(\alpha-\beta)D$. Then, for any
$i\in\\{1,2,\ldots,n\\}$ and $j\in\\{0,1,\ldots,n-i\\}$, using Theorem 2.1, we
obtain

$\displaystyle\lambda_{n+1-i}(B_{\alpha})$
$\displaystyle=\lambda_{n+1-i}(B_{\alpha}+B_{\beta}-B_{\beta})$
$\displaystyle\leq\lambda_{n+1-i-j}(B_{\alpha}+B_{\beta})+\lambda_{j+1}(-B_{\beta})$
$\displaystyle=\lambda_{n+1-i-j}(B_{\alpha}+B_{\beta})-\lambda_{n-j}(B_{\beta}).$

Thus, for any $i\in\\{1,2,\ldots,n\\}$ and $j\in\\{0,1,\ldots,n-i\\}$,

$\displaystyle\lambda_{n+1-i}(B_{\alpha})+\lambda_{n-j}(B_{\beta})$
$\displaystyle\leq\lambda_{n+1-i-j}(B_{\alpha}+B_{\beta})\quad\text{ for all
}\alpha,\beta\in[0,1].$ (4)

Assume that $\alpha\leq\beta$. By using (4) and Corollary 2.1, we compute

$\displaystyle\lambda_{k}(B_{\alpha})-\lambda_{k}(B_{\beta})$
$\displaystyle=\lambda_{n+1-k}(-B_{\beta})+\lambda_{n-(n-k)}(B_{\alpha})$
$\displaystyle\leq\lambda_{n+1-k-(n-k)}(-B_{\beta}+B_{\alpha})$
$\displaystyle=\lambda_{1}(B_{\alpha}-B_{\beta})$
$\displaystyle\leq\lambda_{1}(2(\beta-\alpha)L)+\lambda_{1}((\alpha-\beta)D)$
$\displaystyle=2(\beta-\alpha)\lambda_{1}(L)+(\alpha-\beta)\lambda_{n}(D)$
$\displaystyle\leq|\alpha-\beta|(2\lambda_{1}(L)+\lambda_{1}(D)).$

Also, by using (4) and Corollary 2.1, we obtain

$\displaystyle\lambda_{k}(B_{\beta})-\lambda_{k}(B_{\alpha})$
$\displaystyle\leq\lambda_{1}(B_{\beta}-B_{\alpha})$
$\displaystyle\leq\lambda_{1}(2(\alpha-\beta)L)+\lambda_{1}((\beta-\alpha)D)$
$\displaystyle=2(\alpha-\beta)\lambda_{n}(L)+(\beta-\alpha)\lambda_{1}(D)$
$\displaystyle\leq|\alpha-\beta|(2\lambda_{1}(L)+\lambda_{1}(D)).$

Thus,
$|\lambda_{k}(B_{\beta})-\lambda_{k}(B_{\alpha})|\leq|\alpha-\beta|(2\lambda_{1}(L)+\lambda_{1}(D))$.
Hence, the mapping $f_{G}$ is uniformly continuous. ∎

Note that for a graph $G$ (with atleast an edge) on $n$ vertices,
$\lambda_{n}(B_{\frac{1}{2}})=\frac{1}{2}\lambda_{n}(D)\geq 0$ and
$\lambda_{n}(B_{1})=\lambda_{n}(A)\leq 0$. By Theorem 3.1,
$\lambda_{n}(B_{\alpha})$ is continuous, so there exists a $\beta\in(0,1)$
such that $\lambda_{n}(B_{\beta})=0$. Therefore, for a graph $G$ (with atleast
an edge) on $n$ vertices, we define
$\beta_{o}(G):=\max\\{\beta\in(0,1):\lambda_{n}(B_{\beta})=0\\}$. It is simply
denoted by $\beta_{o}$ if the graph $G$ is understood from the context.

######  Theorem 3.2.

If $G$ is a connected graph with $n\,(>1)$ vertices, then $B_{\alpha}$ is
positive definite for $\alpha\in(0,\frac{2}{3})$.

###### Proof.

First we assume that $0<\alpha\leq\frac{1}{2}$. Since $G$ is connected and
$\lambda_{n}(B_{\alpha})=-\lambda_{1}(-B_{\alpha})$, by Corollary 2.1, we
obtain

$\displaystyle\lambda_{n}(B_{\alpha})$
$\displaystyle=\lambda_{n}((1-2\alpha)L+\alpha D)$
$\displaystyle\geq(1-2\alpha)\lambda_{n}(L)+\alpha\lambda_{n}(D)$
$\displaystyle=\alpha\lambda_{n}(D)>0.$

Thus, $B_{\alpha}$ is positive definite for $\alpha\in(0,\frac{1}{2}]$.

Next we assume that $\frac{1}{2}<\alpha<\frac{2}{3}$. Then
$0<2\alpha-1<1-\alpha$. Now $B_{\alpha}=(2\alpha-1)A+(1-\alpha)D$. Let
$(B_{\alpha})_{ij}$ be the $(i,j)$-th entry of $B_{\alpha}$. Then, for
$i\in\\{1,2,\ldots,n\\}$, we have

$\displaystyle|(B_{\alpha})_{ii}|$
$\displaystyle=|(1-\alpha)\,d_{i}|=(1-\alpha)\,d_{i}>(2\alpha-1)\,d_{i}=|2\alpha-1|\,d_{i}=\sum_{j=1,~{}j\neq
i}^{n}|(B_{\alpha})_{ij}|.$

Thus, $B_{\alpha}$ is strictly diagonally dominant with positive diagonal
entries. Also, $B_{\alpha}$ is irreducible. Therefore, by Theorem 2.5,
$B_{\alpha}$ is positive definite for $\alpha\in(\frac{1}{2},\frac{2}{3})$. ∎

######  Corollary 3.1.

If $G$ is a graph with no isolated vertices, then $B_{\alpha}$ is positive
definite for$\alpha\in(0,\frac{2}{3})$.

Next corollary gives a lower bound of $\beta_{o}(G)$. For simplicity, we use
$\beta_{o}$ instead of $\beta_{o}(G)$.

######  Corollary 3.2.

If $G$ is a graph with no isolated vertices, then $\beta_{o}\geq\frac{2}{3}$.

###### Proof.

By Theorem 3.1, $f_{G}(\alpha):=\lambda_{n}(B_{\alpha})$ is continuous. By
Corollary 3.1, $\lambda_{n}(B_{\alpha})>0$ for$\alpha\in(0,\frac{2}{3})$.
Also, $\lambda_{n}(B_{1})<0$. Therefore, $\beta_{o}\geq\frac{2}{3}$. ∎

######  Theorem 3.3.

Let $G$ be a graph with no isolated vertices. Then $B_{\alpha}$ is positive
semidefinite if and only if $\alpha\in[0,\beta_{o}]$.

###### Proof.

Let $G$ be a graph with $n$ vertices $\\{v_{1},v_{2},\dots,v_{n}\\}$. Set
$\beta_{o}:=\beta_{o}(G)$. Suppose $\alpha\in[0,\beta_{o}]$. For
$\alpha\in(0,\frac{2}{3})$, by Corollary 3.1, $B_{\alpha}$ is positive
definite. Assume that $\frac{2}{3}\leq\alpha\leq\beta_{o}$. Then
$-\alpha\geq-\beta_{o}$, that is,
$\alpha\,(2\beta_{o}-1)\geq\beta_{o}\,(2\alpha-1)$ which implies
$\frac{\alpha}{2\alpha-1}\geq\frac{\beta_{o}}{2\beta_{o}-1}$. Note that for
any ${\bf x}=(x_{1},x_{2},\ldots,x_{n})^{t}\in\mathbb{R}^{n}$, we obtain

$\displaystyle{\bf x}^{t}\,B_{\alpha}\,{\bf x}$ $\displaystyle\,=\,{\bf
x}^{t}\,\alpha D\,{\bf x}+{\bf x}^{t}\,(1-2\alpha)L\,{\bf x}$
$\displaystyle\,=\,\alpha\,\sum_{i=1}^{n}\,d_{i}\,x_{i}^{2}+(1-2\alpha)\,\sum_{v_{j}v_{i}\in
E(G)}\,(x_{i}-x_{j})^{2}.$ (5)

Then, for any ${\bf x}=(x_{1},x_{2},\dots,x_{n})^{t}\in\mathbb{R}^{n}$ and
using (3), we obtain

$0\leq{\bf x}^{t}B_{\beta_{o}}{\bf
x}=\beta_{o}\,\sum\limits_{i=1}^{n}\,d_{i}\,x_{i}^{2}+\break(1-2\beta_{o})\sum\limits_{v_{j}v_{i}\in
E(G)}(x_{i}-x_{j})^{2}$

which implies

$\sum\limits_{v_{j}v_{i}\in
E(G)}(x_{i}-x_{j})^{2}\leq\frac{\beta_{o}}{2\beta_{o}-1}\,\sum\limits_{i=1}^{n}\,d_{i}\,x_{i}^{2}\leq\frac{\alpha}{2\alpha-1}\,\sum\limits_{i=1}^{n}\,d_{i}\,x_{i}^{2}.$

Thus,

${\bf x}^{t}B_{\alpha}{\bf
x}=\alpha\sum\limits_{i=1}^{n}\,d_{i}\,x_{i}^{2}+(1-2\alpha)\sum\limits_{v_{j}v_{i}\in
E(G)}(x_{i}-x_{j})^{2}\geq 0\,\mbox{ for any }~{}{\bf x}\in\mathbb{R}^{n}.$

Hence,

$\lambda_{n}(B_{\alpha})=\min\\{{\bf x}^{t}B_{\alpha}{\bf x}:{\bf
x}\in\mathbb{R}^{n},\|{\bf x}\|=1\\}\geq 0.$

Therefore, $B_{\alpha}$ is positive semidefinite for all
$\alpha\in[0,\beta_{o}]$.

To prove the converse, it is enough to prove that if $\alpha\in(\beta_{o},1]$,
then $B_{\alpha}$ is not positive semidefinite. Suppose there exists an
$\alpha\in(\beta_{o},1]$ such that $\lambda_{n}(B_{\alpha})\geq 0$. By Theorem
3.1, the function $f_{G}(\alpha):=\lambda_{n}(B_{\alpha})$ is continuous and
$\lambda_{n}(B_{1})<0$, so there exist a $\beta\in[\alpha,1)$ such that
$\lambda_{n}(B_{\beta})=0$. This contradicts that $\beta_{o}$ is the largest
number in $(0,1)$ for which $\lambda_{n}(B_{\beta_{o}})=0$. Hence,
$\lambda_{n}(B_{\alpha})<0$ for all $\alpha\in(\beta_{o},1]$. ∎

A symmetric matrix $M$ is called indefinite if there exist two nonzero vectors
$x$ and $y$ such that $y^{T}My>0>x^{T}Mx$, where $x^{T}$ denotes the transpose
of $x$.

######  Corollary 3.3.

For a graph $G$ with no isolated vertices, $B_{\alpha}$ is indefinite if and
only if $\alpha\in(\beta_{o},1]$.

###### Proof.

First we assume that $B_{\alpha}$ is indefinite. Set
$\beta_{o}:=\beta_{o}(G)$. Then $\lambda_{1}(B_{\alpha})>0$ and
$\lambda_{n}(B_{\alpha})<0$. Thus, $\alpha\in(\beta_{o},1]$.

Conversely, suppose $\alpha\in(\beta_{o},1]$. Then
$\lambda_{n}(B_{\alpha})<0$. Also, $\alpha>\beta_{o}>\frac{1}{2}$. Hence, by
Corollary 2.1, we have

$\displaystyle\lambda_{1}(B_{\alpha})$
$\displaystyle=\lambda_{1}((2\alpha-1)A+(1-\alpha)D)$
$\displaystyle\geq\lambda_{1}((2\alpha-1)A)+\lambda_{n}((1-\alpha)D)$
$\displaystyle=(2\alpha-1)\lambda_{1}(A)+(1-\alpha)\lambda_{n}(D)$
$\displaystyle>0.$

Hence, $B_{\alpha}$ is indefinite. ∎

In the next theorem, we find $\beta_{o}$ for regular graphs.

######  Theorem 3.4.

If $G$ is an $r$-regular graph with smallest adjacency eigenvalue
$\rho_{n}(G)$. Then

$\beta_{o}(G)=\frac{r-\rho_{n}(G)}{r-2\rho_{n}(G)}.$

###### Proof.

Set $\beta_{o}:=\beta_{o}(G)$. Then

$\displaystyle 0=\lambda_{n}(B_{\beta_{o}})$
$\displaystyle=\lambda_{n}\Big{(}(2\beta_{o}-1)A+(1-\beta_{o})D\Big{)}$
$\displaystyle=\lambda_{n}\Big{(}(2\beta_{o}-1)A+(1-\beta_{o})rI\Big{)}$
$\displaystyle=(2\beta_{o}-1)\lambda_{n}(A)+(1-\beta_{o})r.$

This gives
$\displaystyle{\beta_{o}=\frac{r-\lambda_{n}(A)}{r-2\lambda_{n}(A)}.}$ ∎

Let us recall the following Hoffman bound of independence number $\alpha(G)$
of an $r$-regular graph $G$ with $n$ vertices in terms of $\rho_{n}(G)$.

$\alpha(G)\leq-\frac{\rho_{n}(G)}{r-\rho_{n}(G)}\,n.$

In light of the above result, we obtain a close relation between the
independence number $\alpha(G)$ of a regular graph $G$ and $\beta_{o}(G)$.

######  Proposition 3.2.

Let $G$ be an $r$-regular graph of $n$ vertices with independence number
$\alpha(G)$ and $\beta_{o}:=\beta_{o}(G)$. Then

$\alpha(G)\leq n\left(\frac{1-\beta_{o}}{\beta_{o}}\right).$

##  4 On eigenvalues

The spectral radius of a matrix is the maximum value among the absolute values
of all eigenvalues of that matrix. For any $B_{\alpha}$-matrix, we first show
a partial Perron-Frobenius type result (that is, $\lambda_{1}(B_{\alpha})$ is
the spectral radius of $B_{\alpha}$). Then we compute the eigenvalues of
$B_{\alpha}(G)$ for complete graph and complete bipartite graph. Thereafter,
we obtain some lower and upper bounds on the largest eigenvalue of
$B_{\alpha}(G)$ of graph $G$ in terms of $\Delta$ and $\delta$. As a
consequence, we deduce some known results. In addition, we establish an upper
bound on the smallest eigenvalue of $B_{\alpha}(G)$ in terms of the chromatic
number. Finally, we derive a bound on the chromatic number in terms of
$\beta_{o}(G)$.

It is to be observed that $B_{\alpha}$-matrices are not always non-negative.
Therefore, Perron-Frobenius Theorem is not directly applicable. However, we
can still conclude that the spectral radius of a $B_{\alpha}$-matrix is the
same as its largest eigenvalue.

######  Theorem 4.1.

For any $\alpha\in[0,1]$, the spectral radius of $B_{\alpha}$ of a connected
graph $G$ is $\lambda_{1}(B_{\alpha})$.

###### Proof.

For $\alpha\in[0,\frac{1}{2}]$, $B_{\alpha}$ is positive semidefinite by
Theorem 3.2. Hence, $\lambda_{1}(B_{\alpha})$ is the spectral radius of
$B_{\alpha}$. Let $\alpha\in(\frac{1}{2},1]$. Then $2\alpha-1>0$ and hence
$B_{\alpha}=(2\alpha-1)A+(1-\alpha)D$ is a non-negative matrix. Also,
$B_{\alpha}$ is irreducible. Therefore, by Perron-Frobenius Theorem,
$\lambda_{1}(B_{\alpha})$ is the spectral radius of $B_{\alpha}$. ∎

###  4.1 The spectrum of $B_{\alpha}$-matrix for complete and complete
bipartite graphs

In this subsection, we determine the eigenvalues of $B_{\alpha}$-matrices of
the complete graph and the complete bipartite graph.

######  Proposition 4.1.

If $G$ is a complete graph with $n$ vertices, then eigenvalues of
$B_{\alpha}(G)$ are $(1-\alpha)n-\alpha$ with multiplicity $n-1$ and
$(n-1)\alpha$ with multiplicity $1$.

A complete bipartite graph with vertex partition size $a$ and $b$ is denoted
by $K_{a,b}$. Since the eigenvalues of the adjacency matrix of a complete
bipartite graph are known, so we compute the eigenvalues of
$B_{\alpha}(K_{a,b})$ for $\alpha\in[0,1)$.

######  Proposition 4.2.

For $\alpha\in[0,1)$, the eigenvalues of $B_{\alpha}(K_{a,b})$ are
$(1-\alpha)a$ with multiplicity $b-1$, $(1-\alpha)b$ with multiplicity $a-1$,
and
$\displaystyle{\frac{(1-\alpha)(a+b)\pm\sqrt{(1-\alpha)^{2}(a-b)^{2}+4(2\alpha-1)^{2}ab}}{2}}$.

###### Proof.

Let $J_{a,b}$ and $J_{b,a}$ be the square matrices of order $a\times b$ and
$b\times a$, respectively, of all ones. Then

$\displaystyle B_{\alpha}(K_{a,b})=B_{\alpha}$
$\displaystyle=(2\alpha-1)A+(1-\alpha)D$
$\displaystyle=(2\alpha-1)\left(\begin{array}[]{cc}0&J_{a,b}\\\\[8.53581pt]
J_{b,a}&0\end{array}\right)+(1-\alpha)\left(\begin{array}[]{cc}bI_{a}&0\\\\[8.53581pt]
0&aI_{b}\end{array}\right)$
$\displaystyle=\left(\begin{array}[]{cc}(1-\alpha)bI_{a}&(2\alpha-1)J_{a,b}\\\\[8.53581pt]
(2\alpha-1)J_{b,a}&(1-\alpha)aI_{b}\end{array}\right).$

For $i\in\\{2,3,\ldots,a\\}$, let the vector ${\bf
x^{(i)}}=(x^{i}_{1},x^{i}_{2},\dots,x^{i}_{a+b})^{t}$ of order $a+b$ be
defined as

$\displaystyle x_{j}^{i}=\begin{cases}1\ &\text{ for }j=1,\\\ -1\ &\text{ for
}j=i,\\\ 0\ &\text{ otherwise}.\end{cases}$

Then $\\{{\bf x^{(2)}},{\bf x^{(3)}},\ldots,{\bf x^{(a)}}\\}$ is a linearly
independent set of eigenvectors corresponding to the eigenvalue $(1-\alpha)b$.
Thus, $B_{\alpha}$ has eigenvalue $(1-\alpha)b$ with multiplicity $a-1$.

For $i\in\\{a+2,a+3,\ldots,a+b\\}$, let the vector ${\bf
x^{(i)}}=(x^{i}_{1},x^{i}_{2},\dots,x^{i}_{a+b})^{t}$ of order $a+b$ be
defined as

$\displaystyle x_{j}^{i}=\begin{cases}1\ &\text{ for }j=a+1,\\\ -1\ &\text{
for }j=i,\\\ 0\ &\text{ otherwise}.\end{cases}$

Then $\\{{\bf x^{(a+2)}},{\bf x^{(a+3)}},\ldots,{\bf x^{(a+b)}}\\}$ is a
linearly independent set of eigenvectors corresponding to the eigenvalue
$(1-\alpha)a$. Thus, $B_{\alpha}$ has eigenvalue $(1-\alpha)a$ with
multiplicity $b-1$.

Let $\alpha\in[0,1)$. Then, by using Theorem 2.3, we compute

$\displaystyle\det(B_{\alpha})$
$\displaystyle=\begin{vmatrix}(1-\alpha)\,b\,I_{a}&(2\alpha-1)\,J_{a,b}\\\\[8.53581pt]
(2\alpha-1)\,J_{b,a}&(1-\alpha)\,a\,I_{b}\end{vmatrix}$
$\displaystyle=\det\Big{(}(1-\alpha)\,b\,I_{a}\Big{)}\,\det\left((1-\alpha)a\,I_{b}-(2\alpha-1)\,J_{b,a}\Big{(}(1-\alpha)\,b\,I_{a}\Big{)}^{-1}(2\alpha-1)\,J_{a,b}\right)$
$\displaystyle=(1-\alpha)^{a}\,b^{a}\det\left((1-\alpha)aI_{b}-(2\alpha-1)^{2}J_{b,a}\frac{1}{(1-\alpha)b}I_{a}J_{a,b}\right)$
$\displaystyle=(1-\alpha)^{a}\,b^{a}\det\left((1-\alpha)aI_{b}-\frac{a(2\alpha-1)^{2}}{(1-\alpha)b}J_{b,b}\right)$
$\displaystyle=(1-\alpha)^{a}\,b^{a}(1-\alpha)^{b-1}\,a^{b-1}\left((1-\alpha)\,a-\frac{a\,(2\alpha-1)^{2}}{(1-\alpha)}\right).$

Let $x$ and $y$ be the remaining eigenvalues of $B_{\alpha}(K_{a,b})$. Then

$\displaystyle
xy\,\Big{(}(1-\alpha)\,a\Big{)}^{b-1}\Big{(}(1-\alpha)\,b\Big{)}^{a-1}=(1-\alpha)^{a}\,b^{a}\,(1-\alpha)^{b-1}\,a^{b-1}\left((1-\alpha)\,a-\frac{a\,(2\alpha-1)^{2}}{(1-\alpha)}\right).$

Thus we obtain

$\displaystyle xy$
$\displaystyle=b(1-\alpha)\left((1-\alpha)a-\frac{a(2\alpha-1)^{2}}{(1-\alpha)}\right)$
$\displaystyle=(1-\alpha)^{2}ab-(2\alpha-1)^{2}ab.$ (6)

Since the sum of the eigenvalues is equal to the trace of the matrix, we
obtain

$x+y+(b-1)(1-\alpha)a+(a-1)(1-\alpha)b=(1-\alpha)ab+(1-\alpha)ab,$

that is, $x=(1-\alpha)(a+b)-y$. Substitute the value of $x$ in (4.1), we
obtain

$y^{2}-(1-\alpha)(a+b)y+(1-\alpha)^{2}ab-(2\alpha-1)^{2}ab=0.$

This gives

$y=\frac{(1-\alpha)(a+b)\pm\sqrt{(1-\alpha)^{2}(a-b)^{2}+4(2\alpha-1)^{2}ab}}{2}.$

Hence the eigenvalues of $B_{\alpha}(K_{a,b})$ are $(1-\alpha)a$ with
multiplicity $b-1$, $(1-\alpha)b$ with multiplicity $a-1$ and
$\displaystyle{\frac{(1-\alpha)(a+b)\pm\sqrt{(1-\alpha)^{2}(a-b)^{2}+4(2\alpha-1)^{2}ab}}{2}.}$
∎

###  4.2 Bounds on the largest eigenvalue

For a connected graph $G$ with vertex set
$V(G)=\\{v_{1},v_{2},\dots,v_{n}\\}$, the distance between two vertices
$v_{i}$ and $v_{j}$ is denoted by $d(v_{i},v_{j})$ and is defined to be the
length of the shortest path between them. We now establish some lower and
upper bounds on the largest eigenvalue of $B_{\alpha}(G)$ of graph $G$.

######  Theorem 4.2.

Let $G$ be a connected graph with the minimum degree $\delta$. Then, for any
$\alpha\in[0,1]$

$\lambda_{1}(B_{\alpha})\geq\alpha\delta.$

###### Proof.

First we assume that $\alpha\in[0,\frac{1}{2}]$, that is, $2\alpha-1\leq 0$.
Let ${\bf x}=(x_{1},x_{2},\dots,x_{n})^{t}\in\mathbb{R}^{n}$ be an eigenvector
of $B_{\alpha}$ corresponding to $\lambda_{1}(B_{\alpha})$ such that
$x_{k}=\min\limits_{1\leq i\leq n}\,x_{i}<0$. Then

$\displaystyle\lambda_{1}(B_{\alpha})\,x_{k}$
$\displaystyle=(2\alpha-1)\sum\limits_{v_{j}:v_{k}v_{j}\in
E(G)}x_{j}+(1-\alpha)d_{k}x_{k}\leq(2\alpha-1)\,d_{k}x_{k}+(1-\alpha)d_{k}\,x_{k}=\alpha
d_{k}x_{k}.$

Therefore, $\lambda_{1}(B_{\alpha})\geq\alpha d_{k}\geq\alpha\delta$.

Next we assume that $\alpha\in(\frac{1}{2},1]$, that is, $2\alpha-1>0$. Then
$B_{\alpha}$ is irreducible and non-negative. Therefore, by Perron-Frobenius
Theorem, $B_{\alpha}$ has a Perron eigenvector ${\bf
x}=(x_{1},x_{2},\dots,x_{n})^{t}>0$ corresponding to the eigenvalue
$\lambda_{1}(B_{\alpha})$. Let $x_{k}=\min\limits_{1\leq i\leq n}\,x_{i}>0$.
Then we have

$\displaystyle\lambda_{1}(B_{\alpha})x_{k}$
$\displaystyle=(2\alpha-1)\sum_{v_{j}:v_{j}v_{k}\in
E(G)}x_{j}+(1-\alpha)d_{k}x_{k}\geq(2\alpha-1)d_{k}x_{k}+(1-\alpha)d_{k}x_{k}=\alpha
d_{k}x_{k}.$

Thus, $\lambda_{1}(B_{\alpha})\geq\alpha d_{k}\geq\alpha\delta$, for
$\alpha\in(\frac{1}{2},1]$. Hence, $\lambda_{1}(B_{\alpha})\geq\alpha\delta$
for all $\alpha\in[0,1]$. ∎

Let $N_{G}(v_{1})$ denote the set of vertices of $G$ which are adjacent to
$v_{1}$. Let $N_{G}[v_{1}]:=N_{G}(v_{1})\cup\\{v_{1}\\}$.

######  Theorem 4.3.

Let $G$ be a graph with at least one edge and maximum degree $\Delta$. Then,
for any $\alpha\,(\neq\frac{1}{2})\in[0,1]$,

$\lambda_{1}(B_{\alpha})\geq\frac{Y}{Z},$

where $Y$ and $Z$ are given by

$\displaystyle Y=$
$\displaystyle\Big{[}\alpha^{2}\,(3\alpha-1)^{2}\,(\Delta+1)^{2}\,\Big{(}2\alpha\,m_{2}+(1-\alpha)\,m_{3}\Big{)}+(1-\alpha)\,(2\alpha-1)^{2}\,(2\Delta+5\alpha-3\alpha^{2})^{2}\,\Delta\Big{]}\,P^{2}$
$\displaystyle+4\,(2\alpha-1)^{2}\,(\Delta+1)\Big{[}(2\alpha-1)\,\Delta\,(2\Delta+5\alpha-3\alpha^{2})+\alpha\,(3\alpha-1)\,(\Delta+1)\,m_{3}\Big{]}\,PQ$
$\displaystyle+4\,(2\alpha-1)^{2}\,(\Delta+1)^{2}\,\Big{[}2\alpha\,m_{1}+(1-\alpha)\,(\Delta+m_{3})\Big{]}\,Q^{2},$
(7) $\displaystyle
Z=\Big{[}(2\alpha-1)^{2}\,(2\Delta+5\alpha-3\alpha^{2})^{2}+\alpha^{2}\,(3\alpha-1)^{2}\,(\Delta+1)^{2}\,(n-\Delta-1)\Big{]}\,P^{2}+4\Delta\,(\Delta+1)^{2}\,(2\alpha-1)^{2}\,Q^{2}$
(8)

with

$\displaystyle
P=(2\alpha-1)\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}~{}\mbox{ and
}~{}Q=16\alpha^{2}-6\alpha^{3}-10\alpha+2,$ (9)

and $m_{1}=|E(N_{G}(v_{1}))|$, is the number of edges in the set
$N_{G}(v_{1})$, $m_{2}=|E(V(G)\backslash N_{G}[v_{1}])|$, is the number of
edges in the set $V(G)\backslash N_{G}[v_{1}]$, $m_{3}$ is the number of edges
between $N_{G}(v_{1})$ and $V(G)\backslash N_{G}[v_{1}]$, and the vertex
$v_{1}$ has degree $\Delta$.

###### Proof.

Let $v_{1}$ be the maximum degree vertex of degree $\Delta$ in $G$. Also let
$S=\\{v_{2},v_{3},\ldots,v_{\Delta+1}\\}$ be the set of vertices adjacent to
$v_{1}$ in $G$. Let ${\bf x}=(x_{1},x_{2},\ldots,x_{n})^{t}$ be any non-zero
vector. Using Rayleigh quotient, we obtain

$\displaystyle{\bf x}^{t}B_{\alpha}{\bf x}\leq\lambda_{1}(B_{\alpha}){\bf
x}^{t}{\bf x},~{}\mbox{ that is,
}~{}\lambda_{1}(B_{\alpha})\geq\frac{2\,\alpha\,\sum\limits_{v_{i}v_{j}\in
E(G)}\,x_{i}x_{j}+(1-\alpha)\,\sum\limits_{v_{i}v_{j}\in
E(G)}\,(x_{i}-x_{j})^{2}}{\sum\limits^{n}_{i=1}\,x^{2}_{i}}.$ (10)

We consider the following two cases:

${\bf Case\,1.}$ $(\alpha-1)\,(3\alpha-2)\,\Delta+2\neq 0$. In this case
$P=(2\alpha-1)\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}\neq 0$ as
$\alpha\neq\frac{1}{2}$. Setting

$x_{i}=\left\\{\begin{array}[]{ll}\displaystyle{1-\frac{2-5\alpha+3\alpha^{2}}{2(\Delta+1)}}&\hbox{for
$i=1$,}\\\\[14.22636pt]
\displaystyle{\frac{16\alpha^{2}-6\alpha^{3}-10\alpha+2}{(2\alpha-1)\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}}}&\hbox{for
$i=2,3,\ldots,\Delta+1$,}\\\\[19.91692pt]
\displaystyle{\frac{\alpha(3\alpha-1)}{2(2\alpha-1)}}&\hbox{Otherwise.}\end{array}\right.$
(11)

Since $m_{1}=|E(N_{G}(v_{1}))|$, $m_{2}=|E(V(G)\backslash N_{G}[v_{1}])|$, and
$m_{3}$ is the number of edges between $N_{G}(v_{1})$ and $V(G)\backslash
N_{G}[v_{1}]$, we obtain

$\displaystyle\sum\limits_{v_{i}v_{j}\in E(G)}\,x_{i}x_{j}$
$\displaystyle=\frac{(2\Delta+5\alpha-3\alpha^{2})\,(16\alpha^{2}-6\alpha^{3}-10\alpha+2)}{2(\Delta+1)\,(2\alpha-1)\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}}\,\Delta$
$\displaystyle~{}~{}~{}~{}+\frac{(16\alpha^{2}-6\alpha^{3}-10\alpha+2)^{2}}{(2\alpha-1)^{2}\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}^{2}}\,m_{1}+\frac{\alpha^{2}\,(3\alpha-1)^{2}}{4\,(2\alpha-1)^{2}}\,m_{2}$
$\displaystyle~{}~{}~{}~{}+\frac{\alpha(3\alpha-1)\,(16\alpha^{2}-6\alpha^{3}-10\alpha+2)}{2(2\alpha-1)^{2}\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}}\,m_{3},$

$\displaystyle\sum\limits_{v_{i}v_{j}\in E(G)}\,(x_{i}-x_{j})^{2}$
$\displaystyle=\left(\frac{(2\Delta+5\alpha-3\alpha^{2})}{2(\Delta+1)}-\frac{16\alpha^{2}-6\alpha^{3}-10\alpha+2}{(2\alpha-1)\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}}\right)^{2}\,\Delta$
$\displaystyle~{}~{}~{}~{}~{}+\left(\frac{16\alpha^{2}-6\alpha^{3}-10\alpha+2}{(2\alpha-1)\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}}-\frac{\alpha(3\alpha-1)}{2(2\alpha-1)}\right)^{2}\,m_{3},$

and

$\displaystyle\sum\limits^{n}_{i=1}\,x^{2}_{i}$
$\displaystyle=\frac{(2\Delta+5\alpha-3\alpha^{2})^{2}}{4(\Delta+1)^{2}}+\frac{(16\alpha^{2}-6\alpha^{3}-10\alpha+2)^{2}}{(2\alpha-1)^{2}\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}^{2}}\,\Delta+\frac{\alpha^{2}(3\alpha-1)^{2}}{4(2\alpha-1)^{2}}\,(n-\Delta-1).$

Using the above results in (10), we obtain

$\lambda_{1}(B_{\alpha})\geq\frac{Y}{Z}$

as

$\displaystyle 2\,\alpha\,\sum\limits_{v_{i}v_{j}\in
E(G)}\,x_{i}x_{j}+(1-\alpha)\,\sum\limits_{v_{i}v_{j}\in
E(G)}\,(x_{i}-x_{j})^{2}=\frac{Y}{4\,(2\alpha-1)^{2}\,(\Delta+1)^{2}\,P^{2}}$

and

$\displaystyle\sum\limits^{n}_{i=1}\,x^{2}_{i}=\frac{Z}{4\,(2\alpha-1)^{2}\,(\Delta+1)^{2}\,P^{2}},$

where $Y$, $Z$ and $P$ are given by (7), (8) and (9), respectively. Moreover,
the equality holds if and only if ${\bf x}=(x_{1},x_{2},\ldots,x_{n})^{t}$ is
an eigenvector corresponding to the eigenvalue $\lambda_{1}(B_{\alpha})$ of
$B_{\alpha}$, where $x_{i}$ is given in (11).

${\bf Case\,2.}$ $(\alpha-1)\,(3\alpha-2)\,\Delta+2=0$. In this case
$P=(2\alpha-1)\,\Big{(}(\alpha-1)\,(3\alpha-2)\,\Delta+2\Big{)}=0$. In this
case

$Y=4\,(2\alpha-1)^{2}\,(\Delta+1)^{2}\,\Big{[}2\alpha\,m_{1}+(1-\alpha)\,(\Delta+m_{3})\Big{]}\,Q^{2}~{}~{}\mbox{
and }~{}~{}Z=4\Delta\,(\Delta+1)^{2}\,(2\alpha-1)^{2}\,Q^{2}.$

Setting

$x_{i}=\left\\{\begin{array}[]{ll}0&\hbox{for $i=1$,}\\\\[5.69054pt]
1&\hbox{for $i=2,3,\ldots,\Delta+1$,}\\\\[5.69054pt]
0&\hbox{Otherwise.}\end{array}\right.$

Since $m_{1}=|E(N_{G}(v_{1}))|$, $m_{2}=|E(V(G)\backslash N_{G}[v_{1}])|$, and
$m_{3}$ is the number of edges between $N_{G}(v_{1})$ and $V(G)\backslash
N_{G}[v_{1}]$, we obtain

$\displaystyle\sum\limits_{v_{i}v_{j}\in
E(G)}\,x_{i}x_{j}=m_{1},~{}~{}\sum\limits_{v_{i}v_{j}\in
E(G)}\,(x_{i}-x_{j})^{2}=\Delta+m_{3}~{}\mbox{ and
}~{}\sum\limits^{n}_{i=1}\,x^{2}_{i}=\Delta.$

Using the above results in (10), we obtain

$\lambda_{1}(B_{\alpha})\geq\frac{2\,\alpha\,m_{1}+(1-\alpha)\,(\Delta+m_{3})}{\Delta}=\frac{Y}{Z}.$

Moreover, the equality holds if and only if ${\bf
x}=(0,\underbrace{1,\ldots,\,1}_{\Delta},\underbrace{0,\ldots,\,0}_{n-\Delta-1})^{t}$
is an eigenvector corresponding to the eigenvalue $\lambda_{1}(B_{\alpha})$ of
$B_{\alpha}$. ∎

######  Corollary 4.1.

Let $G$ be a graph of order $n$ with $m$ edges and maximum degree $\Delta$.
Then

$\rho_{1}(G)\geq\frac{2m}{n}$

with equality if and only if $G$ is a regular graph.

###### Proof.

For adjacency matrix, $\alpha=1$, that is, $B_{1}=B_{1}(G)=A(G)$. For
$\alpha=1$, from Theorem 4.3, we obtain

$P=2=Q,~{}Y=32\,(\Delta+1)^{2}\,(\Delta+m_{1}+m_{2}+m_{3})=32\,(\Delta+1)^{2}\,m~{}\mbox{
and }~{}Z=16\,(\Delta+1)^{2}\,n$

and hence

$\rho_{1}(G)=\lambda_{1}(B_{1})\geq\frac{Y}{Z}=\frac{2m}{n}.$

Moreover, the equality holds if and only if ${\bf
x}=\left(1,1,\ldots,1\right)^{t}$ is an eigenvector corresponding to the
eigenvalue $\lambda_{1}(B_{1})\,(=\rho_{1}(G))$ of $B_{1}$, that is, if and
only if $G$ is a regular graph. ∎

######  Corollary 4.2.

Let $G$ be a graph of order $n$ with $m$ edges and maximum degree $\Delta$.
Then

$\mu_{1}(G)\geq\Delta+1.$

If $G$ is connected, then the above equality holds if and only if
$\Delta=n-1$.

###### Proof.

For Laplacian matrix, $\alpha=0$, that is, $B_{0}=B_{0}(G)=L(G)$. For
$\alpha=0$, from Theorem 4.3, we obtain

$P=-2\,(\Delta+1),~{}Q=2,~{}Y=16\,\Delta(\Delta+1)^{2}\,\Big{(}(\Delta+1)^{2}+\frac{m_{3}}{\Delta}\Big{)}~{}\mbox{
and }~{}Z=16\,\Delta\,(\Delta+1)^{3}.$

and hence

$\mu_{1}(G)=\lambda_{1}(B_{0})\geq\frac{Y}{Z}=\Delta+1+\frac{m_{3}}{\Delta\,(\Delta+1)}\geq\Delta+1$

as $m_{3}\geq 0$.

Suppose that $G$ is connected. Then the equality holds if and only if ${\bf
x}=\left(\displaystyle{\frac{\Delta}{\Delta+1}},\underbrace{-\frac{1}{\Delta+1},\ldots,-\frac{1}{\Delta+1}}_{\Delta},\underbrace{0,\ldots,0}_{n-\Delta-1}\right)^{t}$
is an eigenvector corresponding to the eigenvalue
$\lambda_{1}(B_{0})\,(=\mu_{1}(G))$ of $B_{0}$ and $m_{3}=0$. Since $G$ is
connected, then $\Delta=n-1$. If $\Delta=n-1$, then one can easily see that
$\mu_{1}(G)=n=\Delta+1$. This completes the proof of the result. ∎

######  Corollary 4.3.

Let $G$ be a graph of order $n$ with $m$ edges and maximum degree $\Delta$.
Then

$q_{1}(G)\geq\frac{4m}{n}$

with equality if and only if $G$ is a regular graph.

###### Proof.

For signless Laplacian matrix, $\alpha=\frac{2}{3}$, that is,
$B_{2/3}=B_{2/3}(G)=\frac{1}{3}\,Q(G)$. For $\alpha=\frac{2}{3}$, from Theorem
4.3, we obtain

$P=\frac{2}{3}=Q,~{}Y=\frac{64}{243}\,(\Delta+1)^{2}\,(\Delta+m_{1}+m_{2}+m_{3})=\frac{64}{243}\,(\Delta+1)^{2}\,m,~{}\mbox{
and }~{}Z=\frac{16}{81}\,(\Delta+1)^{2}\,n$

and hence

$\frac{1}{3}\,q_{1}(G)=\lambda_{1}(B_{2/3})\geq\frac{Y}{Z}=\frac{4m}{3n},~{}\mbox{
that is, }~{}q_{1}(G)\geq\frac{4m}{n}.$

Moreover, the equality holds if and only if ${\bf
x}=\left(1,1,\ldots,1\right)^{t}$ is an eigenvector corresponding to the
eigenvalue $\lambda_{1}(B_{2/3})\,(=\frac{1}{3}\,q_{1}(G))$ of $B_{2/3}$, that
is, if and only if $G$ is a regular graph. ∎

The lower bounds found in Corollaries 4.1-4.3 are classical. One can find all
of them in [27].

######  Remark 4.1.

In the following Table, we give a comparison between the exact value of
$\lambda_{1}(B_{\alpha})$ (Proposition 4.2) and the lower bound on
$\lambda_{1}(B_{\alpha})$ obtained in Theorem 4.3 for the graph $G=K_{1,24}$.

$\alpha$ |  Exact value of $\lambda_{1}(B_{\alpha})$ |  $\frac{Y}{Z}$
---|---|---
$0$ | $25$ | $25$
$0.1$ | $22.317$ | $22.317$
$0.2$ | $19.658$ | $19.654$
$0.3$ | $17.035$ | $16.997$
$0.4$ | $14.469$ | $13.675$
$0.6$ | $9.703$ | $1.978$
$0.7$ | $7.718$ | $0.936$
$0.8$ | $6.232$ | $0.250$
$0.9$ | $5.334$ | $0.361$
$1$ | $4.899$ | $1.92$

Table 1. Comparison of the largest eigenvalue $\lambda_{1}(B_{\alpha})$ and
$\frac{Y}{Z}$.

Next, we observe that the following upper bound is continuous on $\alpha$.

######  Theorem 4.4.

Let $G$ be a connected graph with maximum degree $\Delta$. Then, for any
$\alpha\in[0,1]$,

$\displaystyle\lambda_{1}\,(B_{\alpha})\leq\begin{cases}(2-3\,\alpha)\,\Delta\
\text{ if}~{}\alpha\in[0,\frac{1}{2}],\\\\[8.53581pt] \alpha\,\Delta\
~{}~{}~{}~{}~{}~{}~{}~{}\text{ if}~{}\alpha\in(\frac{1}{2},1].\end{cases}$

###### Proof.

First we assume that $\alpha\in[0,\frac{1}{2}]$. Then, by using $\alpha\geq
0$, $(1-2\alpha)\geq 0$, Corollary 2.1, and Theorem 2.2, we have

$\displaystyle\lambda_{1}(B_{\alpha})=\lambda_{1}\Big{(}\alpha
D+(1-2\alpha)L\Big{)}$ $\displaystyle\leq\lambda_{1}(\alpha
D)+\lambda_{1}\Big{(}(1-2\alpha)L\Big{)}\leq\alpha\Delta+(1-2\alpha)(2\Delta).$

That is, $\lambda_{1}(B_{\alpha})\leq(2-3\alpha)\Delta$ for all
$\alpha\in[0,\frac{1}{2}]$.

Next we assume that $\alpha\in(\frac{1}{2},1]$. That is, $2\alpha-1>0$. Let
${\bf x}=(x_{1},x_{2},\dots,x_{n})^{t}$ be an eigenvector of $B_{\alpha}$
corresponding to the eigenvalue $\lambda_{1}(B_{\alpha})$ such that
$x_{k}=\max\limits_{1\leq i\leq n}\,x_{i}>0$. Then we obtain

$\displaystyle\lambda_{1}(B_{\alpha})\,x_{k}\,$
$\displaystyle\,=(2\alpha-1)\sum_{v_{j}:v_{j}v_{k}\in
E(G)}x_{j}+(1-\alpha)\,d_{k}\,x_{k}$
$\displaystyle\,\leq\,(2\alpha-1)\,d_{k}\,x_{k}+(1-\alpha)\,d_{k}\,x_{k}$
$\displaystyle\,=\,\alpha d_{k}\,x_{k}$ $\displaystyle\,\leq\,\alpha\Delta
x_{k}.$

Therefore, $\lambda_{1}(B_{\alpha})\leq\alpha\Delta$ for all
$\alpha\in(\frac{1}{2},1]$. ∎

For $\alpha\in[0,1]$ and non-negative integers $a$ and $b$, define
$f_{\alpha}(a,b)=\frac{(1-\alpha)\,(a+b)+\sqrt{(1-\alpha)^{2}\,(a-b)^{2}+4(2\alpha-1)^{2}\,ab}}{2}.$

######  Theorem 4.5.

Let $G=(U,\,W,\,E)$ be a connected bipartite graph, where $|U|=a,$ $|W|=b$.
For $\alpha\in[0,1]$,

$\lambda_{1}(B_{\alpha})\leq f_{\alpha}(a,b)$ (12)

with equality if and only if $G\cong K_{a,b}$.

###### Proof.

Without loss of generality, assume that $a\geq b$. Now, from Proposition 4.2,
we have $f_{\alpha}(a,b)=\lambda_{1}(B_{\alpha}(K_{a,b}))$. Since, by
definition, $B_{0}=B_{0}(G)=L(G)$ and $G\subseteq K_{a,b}$, by (edge)
interlacing and Proposition 4.2,

$\lambda_{1}(B_{0})=\mu_{1}(G)\leq a+b=f_{0}(a,b).$

Since $B_{\frac{1}{2}}=B_{\frac{1}{2}}(G)=\frac{1}{2}\,D(G)$, we have

$\lambda_{1}(B_{\frac{1}{2}})=\frac{1}{2}\Delta(G)\leq\frac{1}{2}\Delta(K_{a,b})=\frac{1}{2}\,a=f_{\frac{1}{2}}(a,b).$

As $B_{1}=B_{1}(G)=A(G)$, by (vertex) interlacing and Proposition 4.2, we have

$\lambda_{1}(B_{1})=\rho_{1}(G)\leq\rho_{1}(K_{a,b})=f_{1}(a,b).$

So we have to prove the result in (12) for $0<\alpha<\frac{1}{2}$ and
$\frac{1}{2}<\alpha<1$. Let ${\bf x}=(x_{1},x_{2},\ldots,x_{n})^{T}$ be an
eigenvector corresponding to the largest eigenvalue $\lambda_{1}(B_{\alpha})$
of $B_{\alpha}$. Then $B_{\alpha}{\bf x}=\lambda_{1}(B_{\alpha}){\bf x}$. We
consider two cases:

${\bf Case\,1.}$ $\frac{1}{2}<\alpha<1$. Let $x_{i}=\max\limits_{1\leq k\leq
n}\,x_{k}$. Without loss of generality, we can assume that $v_{i}\in U$. Let
$x_{j}=\max\limits_{v_{k}\in W}\,x_{k}$. For $v_{i}\in U$, we obtain

$\lambda_{1}(B_{\alpha})\,x_{i}=(1-\alpha)\,d_{i}x_{i}+(2\alpha-1)\,\sum\limits_{v_{k}:v_{i}v_{k}\in
E(G)}\,x_{k}\leq(1-\alpha)\,d_{i}x_{i}+(2\alpha-1)\,d_{i}x_{j},$

that is,

$\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{i}\Big{]}\,x_{i}\leq(2\alpha-1)\,d_{i}x_{j}.$
(13)

Similarly, for $v_{j}\in W$, we obtain

$\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{j}\Big{]}\,x_{j}\leq(2\alpha-1)\,d_{j}x_{i}.$
(14)

From the above two results, we obtain

$\displaystyle\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,b\Big{]}\,\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,a\Big{]}$
$\displaystyle\leq$
$\displaystyle\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{i}\Big{]}\,\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{j}\Big{]}$
$\displaystyle\leq$
$\displaystyle(2\alpha-1)^{2}\,d_{i}\,d_{j}\leq(2\alpha-1)^{2}\,ab.$ (15)

Thus we obtain

$\lambda_{1}(B_{\alpha})^{2}-(1-\alpha)\,(a+b)\lambda_{1}(B_{\alpha})+(1-\alpha)^{2}\,ab-(2\alpha-1)^{2}\,ab\leq
0,$

that is,

$\lambda_{1}(B_{\alpha})\leq\frac{(1-\alpha)\,(a+b)+\sqrt{(1-\alpha)^{2}\,(a-b)^{2}+4(2\alpha-1)^{2}\,ab}}{2}=f_{\alpha}(a,b).$

The first part of the proof is done.

Suppose that equality holds. Then all inequalities in the above argument must
be equalities. From equalities in (13) and (14), we obtain $x_{k}=x_{i}$ for
all $v_{k}\in N_{G}(v_{j})\subseteq U$ and $x_{\ell}=x_{j}$ for all
$v_{\ell}\in N_{G}(v_{i})\subseteq W$. From equality in (15), we obtain
$d_{i}=b$ and $d_{j}=a$. Since $G$ is a connected bipartite graph, one can
easily prove that $x_{k}=x_{i}$ for all $v_{k}\in U$ and $x_{\ell}=x_{j}$ for
all $v_{\ell}\in W$. For $v_{i},\,v_{k}\in U$, we have

$\lambda_{1}(B_{\alpha})\,x_{i}=(1-\alpha)\,d_{i}x_{i}+(2\alpha-1)\,\sum\limits_{v_{k}:v_{i}v_{k}\in
E(G)}\,x_{k}=b\,\Big{[}(1-\alpha)\,x_{i}+(2\alpha-1)\,x_{j}\Big{]}$

and

$\lambda_{1}(B_{\alpha})\,x_{i}=d_{k}\,\Big{[}(1-\alpha)\,x_{i}+(2\alpha-1)\,x_{j}\Big{]}.$

Thus we have

$b\,\Big{[}(1-\alpha)\,x_{i}+(2\alpha-1)\,x_{j}\Big{]}=d_{k}\,\Big{[}(1-\alpha)\,x_{i}+(2\alpha-1)\,x_{j}\Big{]},$

that is,

$\Big{(}b-d_{k}\Big{)}\,\Big{[}(1-\alpha)\,x_{i}+(2\alpha-1)\,x_{j}\Big{]}=0.$

Since all the elements in $B_{\alpha}$ are non-negative, by Perron-Frobenius
theorem in matrix theory, we obtain that all the eigencomponents corresponding
to the spectral radius $\lambda_{1}(B_{\alpha})$ are non-negative. Since $G$
is connected, $x_{i}\geq x_{j}>0$. From the above with $\frac{1}{2}<\alpha<1$,
we must have $d_{k}=b$ for any $v_{k}\in U$. Similarly, $d_{\ell}=a$ for any
$v_{\ell}\in W$. Hence $G\cong K_{a,b}$.

${\bf Case\,2.}$ $0<\alpha<\frac{1}{2}$. Let $x_{i}=\max_{1\leq k\leq
n}\,x_{k}$. Without loss of generality, we can assume that $v_{i}\in U$. Let
$x_{j}=\min_{v_{k}:v_{i}v_{k}\in E(G)}\,x_{k}$. For $v_{i}\in U$, we obtain

$\lambda_{1}(B_{\alpha})\,x_{i}=(1-\alpha)\,d_{i}x_{i}+(2\alpha-1)\,\sum\limits_{v_{k}:v_{i}v_{k}\in
E(G)}\,x_{k}\leq(1-\alpha)\,d_{i}x_{i}+(2\alpha-1)\,d_{i}x_{j},$

that is,

$\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{i}\Big{]}\,x_{i}\leq(2\alpha-1)\,d_{i}x_{j}.$

Similarly, for $v_{j}\in W$, we obtain

$\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{j}\Big{]}\,x_{j}\geq(2\alpha-1)\,d_{j}x_{i}.$

Since $\alpha<\frac{1}{2}$, from the above two results, we obtain

$\displaystyle\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{i}\Big{]}\,\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{j}\Big{]}\,x_{i}$
$\displaystyle\leq$
$\displaystyle(2\alpha-1)\,d_{i}\,\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{j}\Big{]}\,x_{j}$
$\displaystyle\leq$ $\displaystyle(2\alpha-1)^{2}\,d_{i}\,d_{j}\,x_{i},$

that is,

$\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{i}\Big{]}\,\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,d_{j}\Big{]}\leq(2\alpha-1)^{2}\,d_{i}\,d_{j},$

that is,

$\displaystyle\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,b\Big{]}\,\Big{[}\lambda_{1}(B_{\alpha})-(1-\alpha)\,a\Big{]}\leq(2\alpha-1)^{2}\,ab.$

Thus we obtain

$\lambda_{1}(B_{\alpha})^{2}-(1-\alpha)\,(a+b)\lambda_{1}(B_{\alpha})+(1-\alpha)^{2}\,ab-(2\alpha-1)^{2}\,ab\leq
0,$

that is,

$\lambda_{1}(B_{\alpha})\leq\frac{(1-\alpha)\,(a+b)+\sqrt{(1-\alpha)^{2}\,(a-b)^{2}+4(2\alpha-1)^{2}\,ab}}{2}=f_{\alpha}(a,b).$

Suppose that equality holds. Similarly as ${\bf Case\,1}$, one can easily
prove that $G\cong K_{a,b}$.

Conversely, let $G\cong K_{a,b}$. By Proposition 4.2, we obtain

$\lambda_{1}(B_{\alpha})=\frac{(1-\alpha)\,(a+b)+\sqrt{(1-\alpha)^{2}\,(a-b)^{2}+4(2\alpha-1)^{2}\,ab}}{2}=f_{\alpha}(a,b).$

This completes the proof of the theorem. ∎

###  4.3 Bounds on the smallest eigenvalue

We establish an upper bound on the smallest eigenvalue of a
$B_{\alpha}$-matrix in terms of the chromatic number. Then, we characterize
the extremal graphs for some cases. Finally, some known results are derived as
a consequence.

######  Theorem 4.6.

Let $G$ be a graph of $n$ vertices, $m~{}(>0)$ edges and chromatic number
$\chi$. Then, for any $\alpha\in[0,1]$,

$\lambda_{n}\,(B_{\alpha})\,\leq\,\frac{2\,m}{n}\,\left(\frac{\chi\,(1-\alpha)-\alpha}{\chi-1}\right).$
(16)

###### Proof.

Set $B_{\alpha}:=B_{\alpha}(G)$. Partition the vertex set $V(G)$ as $\chi$
number of subsets $V_{1},V_{2},\dots,V_{\chi}$, where each subset contains the
vertices having the same colour. For each $j\in\\{1,2,\dots,\chi\\}$, define a
vector ${\bf x}:=(x_{1},x_{2},\dots,x_{n})^{t}$ as follows:

$x_{i}=\left\\{\begin{array}[]{cc}\chi-1&\mbox{ for $v_{i}\in
V_{j}$}\\\\[8.53581pt] -1&\mbox{ otherwise.}\end{array}\right.$

Then

$||{\bf
x}||\,^{2}=\sum\limits_{i=1}^{n}x_{i}^{2}=(\chi-1)^{2}\,|V_{j}|+(n-|V_{j}|)=\chi\,(\chi-2)\,|V_{j}|+n.$

For $j\in\\{1,2,\dots,\chi\\}$, define $m_{j}=\sum\limits_{v\in V_{j}}d(v)$.
Now,

$\langle B_{\alpha}{\bf x},\,{\bf x}\rangle=\langle(2\alpha-1)\,A{\bf
x},\,{\bf x}\rangle+\langle(1-\alpha)\,D{\bf x},\,{\bf x}\rangle.$

Note that

$\langle A{\bf x},\,{\bf x}\rangle=2\sum\limits_{v_{i}v_{j}\in
E(G)}x_{i}\,x_{j}=2\,(1-\chi)\,m_{j}+2\,(m-m_{j})$

and

$\langle D{\bf x},\,{\bf x}\rangle=\sum\limits_{v_{i}\in
V}d_{i}\,x_{i}^{2}\break=(\chi-1)^{2}\,m_{j}+(2m-m_{j})=\chi\,(\chi-2)\,m_{j}+2m.$

Thus we obtain

$\displaystyle\langle B_{\alpha}{\bf x},\,{\bf x}\rangle$
$\displaystyle=(2\alpha-1)\,\langle A{\bf x},\,{\bf
x}\rangle+(1-\alpha)\,\langle D{\bf x},\,{\bf x}\rangle$
$\displaystyle=2\,(2\alpha-1)\,(1-\chi)\,m_{j}+2\,(2\alpha-1)\,(m-m_{j})+(1-\alpha)\,\chi\,(\chi-2)\,m_{j}+2\,(1-\alpha)\,m$
$\displaystyle=2m\,\alpha+\Big{(}\chi-\alpha\,(\chi+2)\Big{)}\,\chi m_{j}.$

Using Rayleigh quotient, we obtain

$\lambda_{n}\,(B_{\alpha})\,||{\bf x}||^{2}\leq\langle B_{\alpha}{\bf
x},\,{\bf x}\rangle.$

Therefore, by the above inequalities, we have

$\lambda_{n}(B_{\alpha})\,\Big{(}\chi\,(\chi-2)\,|V_{j}|+n\Big{)}\leq
2m\alpha+\Big{(}\chi-\alpha\,(\chi+2)\Big{)}\,\chi\,m_{j},$

that is,

$\sum\limits_{j=1}^{\chi}\lambda_{n}(B_{\alpha})\,\Big{(}\chi\,(\chi-2)\,|V_{j}|+n\Big{)}\,\leq\sum\limits_{j=1}^{\chi}\left(2m\alpha+\Big{(}\chi-\alpha\,(\chi+2)\Big{)}\,\chi\,m_{j}\right),$

that is,

$\lambda_{n}(B_{\alpha})\,\Big{(}(\chi^{2}-2\,\chi)\,n+n\,\chi\Big{)}\leq
2\,\chi^{2}\,m-2\,\alpha\chi^{2}\,m-2\,m\,\chi\,\alpha.$

Therefore,

$\lambda_{n}\,(B_{\alpha})\,\leq\,\frac{2\,m}{n}\,\left(\frac{\chi\,(1-\alpha)-\alpha}{\chi-1}\right).$

∎

In the next couple of results, we partially characterize the graphs attaining
the equality in (16) of Theorem 4.6. The proofs technique is similar to the
one used in [21].

######  Theorem 4.7.

Let $G$ be a bipartite graph of $n$ vertices with $m$ edges. Then, for any
$\alpha\in[0,1]$,

$\lambda_{n}(B_{\alpha})\leq\frac{2m}{n}\,(2-3\alpha).$ (17)

Equality occurs if and only if either $\alpha=\frac{2}{3}$, or $G$ is regular
with $\alpha\geq\frac{1}{2}$.

###### Proof.

Set $\lambda_{n}:=\lambda_{n}(B_{\alpha})$. For any ${\bf
x}=(x_{1},x_{2},\dots,x_{n})^{t}\in\mathbb{R}^{n}$, by Rayleigh quotient, we
obtain

$\lambda_{n}\,{\bf x}^{t}\,{\bf x}\leq{\bf x}^{t}\,B_{\alpha}\,{\bf
x}~{}~{}\mbox{ that is,
}~{}~{}\lambda_{n}\sum\limits_{i=1}^{n}x_{i}^{2}\leq\alpha\sum\limits_{i=1}^{n}\,d_{i}\,x_{i}^{2}+(1-2\alpha)\sum\limits_{v_{i}v_{j}\in
E(G),~{}i<j}(x_{i}-x_{j})^{2}.$

Let $V(G)=V_{1}\cup V_{2}$ be the vertex partition of $G$ such that no two
vertices of $V_{1}$ (resp $V_{2}$) are adjacent. Take ${\bf
x}=(x_{1},x_{2},\dots,x_{n})^{t}$, where the component $x_{i}=1$ if $v_{i}\in
V_{1}$, and $x_{i}=-1$ otherwise. Then

$\lambda_{n}(B_{\alpha})\leq\frac{2m}{n}\,(2-3\alpha).$

The first part of the proof is done.

If the equality holds in (17), then $B_{\alpha}\,{\bf x}=\lambda_{n}{\bf x}$.
Suppose $v_{i}\in V_{1}$ and $v_{j}\in V_{2}$. From the $i$-th and $j$-th
equation of $B_{\alpha}{\bf x}=\lambda_{n}{\bf x}$, we obtain

$\lambda_{n}=d_{i}(2-3\alpha)~{}~{}\mbox{ and
}~{}~{}\lambda_{n}=d_{j}(2-3\alpha),~{}~{}\mbox{ that is,
}~{}~{}(\,d_{i}-d_{j}\,)(2-3\alpha)=0.$

Therefore, for the arbitrariness of $v_{i}$ and $v_{j}$, either
$\alpha=\frac{2}{3}$ or $G$ is regular. If $G$ is $r$-regular and
$\alpha<\frac{1}{2}$, then

$\lambda_{n}(B_{\alpha})=\lambda_{n}\Big{(}(1-\alpha)D+(2\alpha-1)A\Big{)}=(1-\alpha)\,r+(2\alpha-1)\,\rho_{1}=\alpha\,r<\frac{2m}{n}\,(2-3\alpha)$

as $\rho_{1}=r$ ($G$ is bipartite). Hence either $\alpha=\frac{2}{3}$, or $G$
is regular with $\alpha\geq\frac{1}{2}$.

Conversely, let $\alpha=\frac{2}{3}$. Then $Q(G)=3B_{\frac{2}{3}}(G)$ and
hence
$\lambda_{n}(B_{\frac{2}{3}})=\frac{1}{3}\,q_{n}(G)=0=\frac{2m}{n}\,(2-3\alpha)$
as $G$ is bipartite.

Let $G$ be a $r$-regular bipartite graph with $\alpha\geq\frac{1}{2}$. Then
$\rho_{n}=-r$. Since $\alpha\geq\frac{1}{2}$, we obtain

$\lambda_{n}(B_{\alpha})=\lambda_{n}\Big{(}(1-\alpha)D+(2\alpha-1)A\Big{)}=(1-\alpha)\,r+(2\alpha-1)\,\rho_{n}=(2-3\,\alpha)\,r=\frac{2m}{n}\,(2-3\alpha).$

∎

In [21], the authors defined a class of graphs $\Lambda$ in the following:

Let $\Lambda$ be the class of graphs $H=(V,E)$ such that $H$ is a regular
$\chi$-partite graph $(\chi\geq 3)$ with $n/\chi$ vertices in every part,
where $\chi|n$, and every vertex has $\frac{d}{\chi-1}$ adjacent vertices in
every other part ($d$ is the degree of each vertex in $H$).

######  Theorem 4.8.

Let $G$ be a graph with chromatic number $\chi$ such that

$\lambda_{n}\,(B_{\alpha})\,=\,\frac{2\,m}{n}\,\left(\frac{\chi\,(1-\alpha)-\alpha}{\chi-1}\right).$
(18)

where $0\leq\alpha\leq 1$. Then

  * $(1)$

for $\alpha=\frac{1}{2}$, $G$ is regular,

  * $(2)$

for $\chi=2$, $G$ is bipartite with $\alpha=\frac{2}{3}$, or $G$ is regular
bipartite with $\alpha\geq\frac{1}{2}$.

  * $(3)$

for
$\alpha\in[0,1]\,\Big{(}\alpha\neq\,\Big{\\{}\frac{1}{2},\,\frac{\chi}{\chi+1}\Big{\\}},\,\chi\geq
3\Big{)}$, $G\in\Lambda$.

###### Proof.

(1) Suppose that $\alpha=\frac{1}{2}$. Then by Remark 1.1 and (18), we obtain
$\frac{\delta}{2}=\lambda_{n}(B_{\frac{1}{2}})=\frac{m}{n}$, that is,
$2m=n\,\delta$, that is, $n\delta\leq\sum\limits^{n}_{i=1}\,d_{i}=2m=n\delta$,
that is, $\sum\limits^{n}_{i=1}\,d_{i}=n\delta$, that is, $G$ is regular.

(2) Suppose $\chi=2$. Then
$\lambda_{n}(B_{\alpha})=\frac{2m}{n}\,(2-3\alpha)$. By Theorem 4.7, $G$ is
bipartite with $\alpha=\frac{2}{3}$, or $G$ is regular bipartite with
$\alpha\geq\frac{1}{2}$.

(3) We assume that $\alpha\in[0,1]$ and
$\alpha\neq\Big{\\{}\frac{1}{2},\,\frac{\chi}{\chi+1}\Big{\\}}$ with $\chi\geq
3$.

Set $\lambda_{n}:=\lambda_{n}(B_{\alpha})$. Let us partition the vertex set
$V(G)$ into $\chi$ number of color classes $V_{1},V_{2},\dots,V_{\chi}$. For
$j\in\\{1,2\dots,\chi\\}$, define ${\bf
x^{(j)}}:=(x^{j}_{1},\,x^{j}_{2},\ldots,\,x^{j}_{n})$ as follows:

$x^{j}_{i}=\left\\{\begin{array}[]{cc}\chi-1&\mbox{for $v_{i}\in
V_{j}$,}\\\\[8.53581pt] -1&\mbox{otherwise.}\end{array}\right.$

Then by Theorem 4.6,
$\lambda_{n}\,(B_{\alpha})\,\leq\,\frac{2\,m}{n}\,\left(\frac{\chi\,(1-\alpha)-\alpha}{\chi-1}\right)$.
Since equality occurs in the above inequality, so by Rayleigh quotient and
Theorem 4.6, ${\bf x^{(1)}},\dots,{\bf x^{(\chi)}}$ are all eigenvectors of
$B_{\alpha}$ corresponding to the eigenvalue $\lambda_{n}$.

${\bf Claim\,1:}$ $G$ is regular.
Let $1\leq k\neq\ell\leq\chi$. Suppose $v_{s}\in V_{k}$ and $v_{t}\in
V_{\ell}$. Comparing the $s$-th components of the matrix equation
$B_{\alpha}{\bf x^{(k)}}=\lambda_{n}{\bf x^{(k)}}$, we obtain
$\lambda_{n}(\chi-1)=d_{s}\,(\chi-\alpha\chi-\alpha)$. Similarly, comparing
the $t$-th components of the matrix equation $B_{\alpha}{\bf
x}^{(\ell)}=\lambda_{n}{\bf x}^{(\ell)}$, we have
$\lambda_{n}(\chi-1)=d_{t}\,(\chi-\alpha\chi-\alpha)$. Then
$(d_{s}-d_{t})(\chi-\alpha\chi-\alpha)=0.$ Since
$\alpha\neq\frac{\chi}{\chi+1}$ and $v_{s}$, $v_{t}$ are arbitrary, so $G$ is
regular.

${\bf Claim\,2:}$ $|V_{1}|=\cdots=|V_{\chi}|=\frac{n}{\chi}$, where $\chi|n$.
By Claim 1, $G$ is regular, so $\boldsymbol{1}:=(1,1,\dots,1)^{t}$ is an
eigenvector of $B_{\alpha}$. Also, $B_{\alpha}$ is symmetric, so
$\boldsymbol{1}\perp x^{(k)}$ for $k=1,2,\dots,\chi$. Therefore,
$|V_{k}|(\chi-1)+(-1)(n-|V_{k}|)=0$. That is, $|V_{k}|=\frac{n}{\chi}$, for
$k=1,2,\dots,\chi$.

${\bf Claim\,3:}$ Every vertex is adjacent to $\frac{d}{\chi-1}$ vertices in
every other part, where $d$ is the regularity of $G$.
Suppose $v_{s}\in V_{1}$ and it is adjacent with
$r_{2},\,r_{3},\ldots,\,r_{\chi}$ number of vertices in the partitions
$V_{2},\,V_{3},\ldots,\,V_{\chi}$, respectively. For $v_{s}\in V_{1}$, from
$B_{\alpha}{\bf x^{(k)}}=\lambda_{n}\,{\bf x^{(k)}}$, we obtain

$(-1)\lambda_{n}=(1-\alpha)(-1)d_{s}+(2\alpha-1)\,\left(\sum\limits^{\chi}_{i=2,i\neq
k}\,(-1)r_{i}+(\chi-1)r_{k}\right),$

where $2\leq k\leq\chi$. From this we have the following $\chi-1$ equations:

$\displaystyle(-1)\lambda_{n}$
$\displaystyle=(1-\alpha)(-1)d_{s}+(2\alpha-1)\Big{(}(\chi-1)r_{2}+(-1)r_{3}+\cdots+(-1)r_{\chi}\Big{)}$
$\displaystyle(-1)\lambda_{n}$
$\displaystyle=(1-\alpha)(-1)d_{s}+(2\alpha-1)\Big{(}(-1)r_{2}+(\chi-1)r_{3}+\cdots+(-1)r_{\chi}\Big{)}$
$\displaystyle\cdots$ $\displaystyle\cdots\cdots$ $\displaystyle\cdots$
$\displaystyle\cdots\cdots$ $\displaystyle(-1)\lambda_{n}$
$\displaystyle=(1-\alpha)(-1)d_{s}+(2\alpha-1)\Big{(}(-1)r_{2}+(-1)r_{3}+\cdots+(\chi-1)r_{\chi}\Big{)}.$

Since $\alpha\neq\frac{1}{2}$, so from the above, we have
$r_{2}=r_{3}=\cdots=r_{\chi}=\frac{d}{\chi-1}$ as $G$ is regular by ${\bf
Claim\,1}$. Also $v_{s}$ is arbitrary, therefore the ${\bf Claim\,3}$ is done.

Hence $G\in\Lambda$. ∎

In the next result, we partially obtain the converse of the Theorem 4.8. One
can verify that if $\alpha=\frac{1}{2}$ and $G$ is regular, then the equality
(18) holds. Moreover, the equality (18) holds for any bipartite graph with
$\alpha=\frac{2}{3}$, or any regular bipartite graph with
$\alpha\geq\frac{1}{2}$. Therefore, we consider the remaining converse part of
the Theorem 4.8. Since the proof technique of the following result is similar
to [21, Theorem 5.1], so we skip it for the readers.

######  Theorem 4.9.

If $G\in\Lambda$ and $\alpha\,(\neq\frac{1}{2})\in[0,1]$, then
$\displaystyle{\frac{2m}{n}\left(\frac{\chi(1-\alpha)-\alpha}{\chi-1}\right)}$
is an eigenvalue of $B_{\alpha}(G)$ with multiplicity $\chi-1$.

The next result is known (see to [18]); however, it can be deduced from
Theorem 4.6 by taking $\alpha=\frac{2}{3}$.

######  Corollary 4.4.

[18] Let $G$ be graph of order $n$ with $m$ edges and chromatic number $\chi$.
Then

$q_{n}(G)\leq\frac{2m}{n}\left(\frac{\chi-2}{\chi-1}\right).$

######  Corollary 4.5.

Let $G$ be graph of order $n$ with $m$ edges and chromatic number $\chi$ such
that

$q_{n}(G)=\frac{2m}{n}\left(\frac{\chi-2}{\chi-1}\right).$

Then $G$ is either bipartite or $G\in\Lambda$.

###### Proof.

Proof follows from Theorem 4.8. ∎

As a consequence of Theorem 4.6, a lower bound of the chromatic number of $G$
is deduced.

######  Corollary 4.6.

If $G$ is a graph with chromatic number $\chi$ and $\beta_{o}:=\beta_{o}(G)$,
then

$\chi\geq\frac{\beta_{o}}{1-\beta_{o}}.$

##  5 On the determinant

In this short section, we present the determinant and the Sachs-type formula
for the coefficients of the characteristic polynomial of $B_{\alpha}(G)$.
Then, we obtain some known results as a consequence.

A spanning elementary subgraph $H$ of a graph $G$ is a spanning subgraph of
$G$ such that each component of $H$ is either a cycle or an edge. For a
spanning elementary subgraph $H$, $p(H)$ and $c(H)$ denote the number of
components and the number of cycles in $H$, respectively. Now, we present the
well known Harary’s formula [15] for the determinant of the adjacency matrix
of a graph.

######  Proposition 5.1.

Let $G$ be a graph with $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Also let $A(G)$
be the adjacency matrix of $G$. Then,

$\displaystyle\det\,(A(G))=\sum\limits_{H}\,(-1)^{\,n-p(H)}\,2^{\,c(H)},$

where summation is over all spanning elementary subgraphs $H$ of $G$.

Motivated by the notion of spanning elementary subgraphs and for the purpose
of the main result in this section, we define the following.

######  Definition 5.1.

Modified Elementary Subgraph: A subgraph $H$ of a graph $G$ is called a
modified elementary subgraph if each component of $H$ is either a vertex, an
edge, or a cycle.

Let $H$ be a modified elementary subgraph. Denote by $c(H),c_{1}(H),$ and
$c_{2}(H)$ the number of components in a subgraph $H$ which are cycles, edges,
and vertices, respectively. Let $p(H):=c(H)+c_{1}(H)+c_{2}(H)$ be the number
of components in $H$. Also, let $\mathcal{C}_{2}(H)$ be the collection of
isolated vertices in $H$. In the following result, we present a Harary-type
formula [15] for the determinant of $B_{\alpha}$-matrices. For a graph $G$,
since $\det(L(G))=\det(B_{0}(G))=0$, so we derive a formula of
$\det(B_{\alpha}(G))$ for $\alpha\in(0,1]$.

######  Theorem 5.1.

Let $G$ be a graph with $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Then, for any
$\alpha\in(0,1]$,

$\det\,(B_{\alpha}(G))=\sum\limits_{H}\,(-1)^{\,n-p(H)}\,2^{\,c(H)}\,(1-\alpha)^{\,c_{2}(H)}\,(2\alpha-1)^{\,n-c_{2}(H)}\left(\prod_{v_{i}\in\mathcal{C}_{2}(H)}d_{G}(v_{i})\right),$
(19)

where summation is over all spanning modified elementary subgraphs $H$ of $G$.

###### Proof.

Consider $B_{\alpha}(G)=(2\alpha-1)A(G)+(1-\alpha)D(G)=(b_{ij})_{n\times n}$.
We have

$\displaystyle\det\,(B_{\alpha}(G))=\sum\limits_{\pi}\,\text{sgn}(\pi)\,b_{1\pi(1)}\,b_{2\pi(2)}\,\cdots\,b_{n\pi(n)},$
(20)

where summation is over all permutations of $1,2,\ldots,n$. Since every
permutation $\pi$ has a cycle decomposition, so a cycle of length $1$, $2$ and
more corresponds to a vertex, an edge, and a cycle, respectively in the graph
$G$. Thus, each term $b_{1\pi(1)}b_{2\pi(2)}\cdots b_{n\pi(n)}$ corresponds to
a spanning modified elementary subgraph of $G$.

Also, each spanning modified elementary subgraph $H$ corresponds to $2^{c(H)}$
terms in the summation (20) as each cycle is associated to a cyclic
permutation in two ways. If $\pi$ is a permutation corresponding to a spanning
modified elementary subgraph $H$, then

$\displaystyle\text{sgn}\,(\pi)$ $\displaystyle=(-1)^{\,n-\text{number of
cycles in the cyclic decomposition of }\pi}$
$\displaystyle=(-1)^{\,n-c(H)-c_{1}(H)-c_{2}(H)}\,=\,(-1)^{\,n-p(H)}$

and

$\displaystyle b_{1\pi(1)}\,b_{2\pi(2)}\,\cdots\,b_{n\pi(n)}$
$\displaystyle=(1-\alpha)^{c_{2}(H)}\,\left(\prod_{v_{i}\in\mathcal{C}_{2}(H)}d_{G}(v_{i})\right)\,(2\alpha-1)^{2c_{1}(H)}\,(2\alpha-1)^{n-2c_{1}(H)-c_{2}(H)}$
$\displaystyle=(1-\alpha)^{c_{2}(H)}\left(\prod_{v_{i}\in\mathcal{C}_{2}(H)}d_{G}(v_{i})\right)(2\alpha-1)^{n-c_{2}(H)}.$

Therefore,

$\displaystyle\det\,(B_{\alpha}(G))=\sum\limits_{H}(-1)^{\,n-p(H)}\,2^{\,c(H)}\,(1-\alpha)^{c_{2}(H)}\,(2\alpha-1)^{\,n-c_{2}(H)}\,\left(\prod_{v_{i}\in\mathcal{C}_{2}(H)}d_{G}(v_{i})\right),$

where summation is over all spanning modified elementary subgraphs $H$ of $G$
. ∎

In the next corollary, we obtain a Sachs-type formula for the coefficients of
the characteristic polynomial of $B_{\alpha}(G)$.

######  Corollary 5.1.

Let
$\phi(B_{\alpha})=\lambda^{n}+a_{1}\lambda^{n-1}+a_{2}\lambda^{n-2}+\cdots+a_{n-1}\lambda+a_{n}$
be the characteristic polynomial of $B_{\alpha}(G)$. Then

$\displaystyle a_{k}$
$\displaystyle=\sum\limits_{H}\,(-1)^{\,p(H)}\,2^{\,c(H)}\,(1-\alpha)^{c_{2}(H)}\,(2\alpha-1)^{\,n-c_{2}(H)}\left(\prod_{v_{i}\in\mathcal{C}_{2}(H)}d_{G}(v_{i})\right),$

where summation is over all modified elementary subgraphs $H$ of $G$ with $k$
vertices.

###### Proof.

The proof follows from Theorem 5.1 and recalling that $c_{k}$ is $(-1)^{k}$
times the sum of $k\times k$ principal minors of $B_{\alpha}(G)$. ∎

One can observe that Proposition 5.1 can also be deduced as a consequence of
the Theorem 5.1.

######  Corollary 5.2.

Let $G$ be a graph with $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Also let $Q(G)$
be the signless Laplacian matrix of $G$. Then,

$\displaystyle\det\,(Q(G))=\sum\limits_{H}\,(-1)^{\,n-p(H)}\,2^{\,c(H)}\left(\prod_{v_{i}\in\mathcal{C}_{2}(H)}d_{G}(v_{i})\right),$

where summation is over all spanning modified elementary subgraphs $H$ of $G$.

###### Proof.

Setting $\alpha=\frac{2}{3}$ in the formula (19) of Theorem 5.1, we obtain the
result. ∎

## Declaration of competing interest

There are neither conflicts of interest nor competing interests. The authors
have no relevant financial interests.

## Acknowledgements

A. Samanta thanks the National Board for Higher Mathematics (NBHM), Department
of Atomic Energy, India, for financial support in the form of an NBHM Post-
doctoral Fellowship (Sanction Order No. 0204/21/2023/R&D-II/10038). The first
author also acknowledges excellent working conditions in the Theoretical
Statistics and Mathematics Unit, Indian Statistical Institute Kolkata. K. C.
Das is supported by National Research Foundation funded by the Korean
government (Grant No. 2021R1F1A1050646).

## References

  * [1] A. Alhevaz, M. Baghipur, H. A. Ganie, K. C. Das, On the $A_{\alpha}$-spectral radius of connected graphs, _Ars Math. Contemporanea_ 23 (2023) #1.06.
  * [2] R. B. Bapat, Graphs and matrices, Springer, London; Hindustan Book Agency, New Delhi, 2010.
  * [3] F. Belardo, M. Brunetti, A. Ciampella, On the multiplicity of $\alpha$ as an $A_{\alpha}(\Gamma)$-eigenvalue of signed graphs with pendant vertices, _Discrete Math._ 342 (8) (2019) 2223–2233.
  * [4] Y. Chen, D. Li, J. Meng, On the second largest $A_{\alpha}$-eigenvalues of graphs, _Linear Algebra Appl._ 580 (2019) 343–358.
  * [5] Y. Chen, D. Li, J. Meng, On the $A_{\alpha}$-spectral radius of Halin graphs, _Linear Algebra Appl._ 645 (2022) 153–164.
  * [6] E. R. v. Dam, W. H. Haemers, Which graphs are determined by their spectrum$?$ _Linear Algebra Appl._ 373 (2003) 241–272.
  * [7] K. C. Das, An improved upper bound for Laplacian graph eigenvalues, _Linear Algebra Appl._ 368 (2003) 269–278.
  * [8] K. C. Das, Proof of conjecture involving algebraic connectivity and average degree of graphs, _Linear Algebra Appl._ 548 (2018) 172–188.
  * [9] K. C. Das, S.-G. Lee, G.-S. Cheon, On the conjecture for certain Laplacian integral spectrum of graphs, _J Graph Theory_ 63 (2010) 106–113.
  * [10] K. C. Das, M. Liu, Kite graphs determined by their spectra, _Applied Mathematics Computation_ 297 (2017) 74–78.
  * [11] K. C. Das, S. A. Mojallal, V. Trevisan, Distribution of Laplacian eigenvalues of graphs, _Linear Algebra Appl._ 508 (2016) 48–61.
  * [12] M. Einollahzadeh, M. M. Karkhaneei, On the lower bound of the sum of the algebraic connectivity of a graph and its complement, _Jour. Comb. Theory, Series B_ 151 (2021) 235–249.
  * [13] S. M. Fallat, S. J. Kirkland, J. J. Molitierno, M. Neumann, On graphs whose Laplacian matrices have distinct integer eigenvalues, _J Graph Theory_ 50 ( 2005) 162–174.
  * [14] Z. Feng, W. Wei, On the $A_{\alpha}$-spectral radius of graphs with given size and diameter, _Linear Algebra Appl._ 650 (2022) 132–149.
  * [15] F. Harary, The determinant of the adjacency matrix of a graph, _SIAM Rev._ 4 (1962) 202–210.
  * [16] R. A. Horn, C. R. Johnson, Matrix analysis, Second edition, Cambridge University Press, Cambridge, 2013.
  * [17] Z. Jiang, On spectral radii of unraveled balls, _Jour. Comb. Theory, Series B_ 136 (2019) 72–80.
  * [18] L. S. de Lima, C. S. Oliveira, N. M. M. de Abreu, V. Nikiforov, The smallest eigenvalue of the signless Laplacian, _Linear Algebra Appl._ 435 (10) (2011) 2570–2584.
  * [19] L. S. de Lima, C. S. Oliveira, N. M. M. de Abreu, V. Nikiforov, On the least eigenvalue of $A_{\alpha}$-matrix of graphs, _Linear Algebra Appl._ 586 (2020) 347–376.
  * [20] H. Lin, X. Liu, J. Xue, Graphs determined by their $A_{\alpha}$-spectra, _Discrete Math._ 342 (2) (2019) 441–450.
  * [21] S. Liu, K. C. Das, S. Sun, J. Shu, On the least eigenvalue of $A_{\alpha}$-matrix of graphs, _Linear Algebra Appl._ 586 (2020) 347–376.
  * [22] S. Liu, K. C. Das, J. Shu, On the eigenvalues of $A_{\alpha}$-matrix of graphs, _Discrete Math._ 343 (8) (2020) 111917.
  * [23] X. Liu, S. Liu, On the $A_{\alpha}$-characteristic polynomial of a graph, _Linear Algebra Appl._ 546 (2018) 274–288.
  * [24] V. Nikiforov, Merging the $A$\- and $Q$-spectral theories, _Appl. Anal. Discrete Math._ 11 (2017) 81–107.
  * [25] V. Nikiforov, O. Rojo, A note on the positive semidefiniteness of $A_{\alpha}(G)$, _Linear Algebra Appl._ 519 (2017) 156–163.
  * [26] A. Samanta, On bounds of $A_{\alpha}$-eigenvalue multiplicity and the rank of a complex unit gain graph, _Discrete Math._ 346 (9) (2023) 113503.
  * [27] Z. Stanić, Inequalities for graph eigenvalues, London Math. Soc. Lecture Note Ser., vol. 423, Cambridge University Press, Cambridge, 2015.
  * [28] M. Zhai, H. Lin, Spectral extrema of $K_{s,t}$-minor free graphs - On a conjecture of M. Tait, _Jour. Comb. Theory, Series B_ 157 (2022) 184–215.