ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.10 https://doi.org/10.26493/1855-3974.3163.6hw (Also available at http://amc-journal.eu) Unifying adjacency, Laplacian, and signless Laplacian theories* Aniruddha Samanta † Theoretical Statistics and Mathematics Unit, Indian Statistical Institute, Kolkata-700108, India Deepshikha Department of Mathematics, Shyampur Siddheswari Mahavidyalaya, University of Calcutta, West Bengal 711312, India Kinkar Chandra Das ‡ Department of Mathematics, Sungkyunkwan University, Suwon 16419, Republic of Korea Received 15 July 2023, accepted 19 May 2024, published online 17 October 2024 Abstract Let G be a simple graph with associated diagonal matrix of vertex degrees D(G), ad- jacency matrix A(G), Laplacian matrix L(G) and signless Laplacian matrix Q(G). Re- cently, Nikiforov proposed the family of matrices Aα(G) defined for any real α ∈ [0, 1] as Aα(G) := αD(G) + (1 − α)A(G), and also mentioned that the matrices Aα(G) can underpin a unified theory of A(G) and Q(G). Inspired from the above definition, we in- troduce the Bα-matrix of G, Bα(G) := αA(G) + (1 − α)L(G) for α ∈ [0, 1]. Note that L(G) = B0(G), D(G) = 2B 1 2 (G), Q(G) = 3B 2 3 (G), A(G) = B1(G). In this arti- cle, we study several spectral properties of Bα-matrices to unify the theories of adjacency, Laplacian, and signless Laplacian matrices of graphs. In particular, we prove that each eigenvalue of Bα(G) is continuous on α. Using this, we characterize positive semidef- inite Bα-matrices in terms of α. 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α(G). As a result, we obtain a bound for the chromatic number *The authors are grateful to the two anonymous referees for their careful reading of this paper and strict criticisms, constructive corrections and valuable comments on this paper, which have considerably improved the presentation of this paper. †The author thanks the National Board for Higher Mathematics (NBHM), Department of Atomic En- ergy, India, for financial support in the form of an NBHM Post-doctoral Fellowship (Sanction Order No. 0204/21/2023/R&D-II/10038). ‡Corresponding author. The author is supported by National Research Foundation funded by the Korean government (Grant No. 2021R1F1A1050646). cb This work is licensed under https://creativecommons.org/licenses/by/4.0/ 2 Ars Math. Contemp. 24 (2024) #P4.10 of G and deduce several known results. In addition, we present a Sachs-type result for the characteristic polynomial of a Bα-matrix. Keywords: Adjacency matrix, Laplacian matrix, signless Laplacian matrix, convex combination,Bα- matrix, Aα-matrix, chromatic number, independence number. Math. Subj. Class. (2020): Primary: 05C50, 05C22; Secondary: 05C35. 1 Introduction Throughout this article, we consider G to be a simple undirected graph with vertex set V (G) = {v1, v2, . . . , vn} and edge set E(G). The adjacency matrix of G is a symmetric n × n matrix A(G) whose (i, j)-th entry is 1 if vi and vj are adjacent, 0 otherwise. The degree matrix of G is a diagonal matrix D(G) whose ith diagonal entry is the degree of the vertex vi. The Laplacian and the signless Laplacian matrix of G are the matrices, L(G) := D(G)−A(G) andQ(G) := D(G)+A(G), respectively. If graphG 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 [8, 14, 28, 18, 13, 27, 7, 9, 10]. 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 α ∈ [0, 1] the Bα-matrix of G is the convex linear combination Bα(G) := αA(G) + (1−α)L(G) (or simply Bα = αA+ (1−α)L, if G is clear from the context). Remark 1.2. Note that L(G) = B0(G), D(G) = 2B 1 2 (G), Q(G) = 3B 2 3 (G), A(G) = B1(G). It is clear that the spectral properties of B1/2(G) and B2/3(G) are equivalent to the spectral properties ofD(G) andQ(G), respectively. In fact,A(G), L(G), Q(G), andD(G) can be considered as the Bα-matrix of G up to proportionality. Therefore, on the one hand, the spectral properties of Bα(G) may reveal the common connection among the spectral properties of all such well-known matrices. On the other hand, Bα(G) may analyze the structural and combinatorial properties of the graph G in a better way. Recently, Nikiforov [23] introduced a family of matrices, known asAα-matrix, which is a convex combination of A(G) and D(G). The theory of Aα-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, 15, 20]), the sec- ond largest eigenvalue [4], the k-th largest eigenvalue [20], the least eigenvalue ([21, 11]), the multiplicity of the eigenvalues ([3, 25]), positive semidefiniteness [24], the characteris- tic polynomial [22], spectral determination of graphs [19], etc. Motivated by Nikiforov’s work, we consider Bα-matrices and study their spectral properties. However, unlike Aα- matrices, Bα-matrices are not always non-negative, but they obey Perron-Frobenius type E-mail addresses: aniruddha.sam@gmail.com (Aniruddha Samanta), dpmmehra@gmail.com (Deepshikha), kinkardas2003@gmail.com (Kinkar Chandra Das) A. Samanta et al.: Unifying adjacency, Laplacian, and signless Laplacian theories 3 results. In this article, we develop the theory of Bα-matrices to unify the theory of adja- cency 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α-matrices. As a consequence, we obtain an upper bound for the independence number. Then we present some bounds of eigenvalues of Bα(G) in terms of maximum degree and minimum degree, chromatic num- ber, 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α(G) in Section 5. 2 Preliminaries Let G be a simple graph with vertex set V (G) = {v1, v2, . . . , vn} and edge set E(G). If two vertices vi and vj are adjacent, we write vi ∼ vj , and vivj denotes the edge between them. The degree of a vertex vi is the number of edges adjacent to vi and is denoted by dG(vi) or simply d(vi) or di. The minimum degree and the maximum degree of graph G are denoted by δ(G) (or simply δ) and ∆(G) (or simply ∆), respectively. The complement of a graph G is the graph G with vertex set V (G) and two vertices in 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 {v1, v2, . . . , vn} andm edges {e1, e2, . . . , em} is an n×mmatrixM whose (i, j)-th entry is 1 if the vertex vi is incident on the edge ej and 0 otherwise. The line graph of a graph G is the graph G` with vertex set E(G) and two vertices ei and ej in G` are adjacent if the edges ei and ej have a common vertex in the graph G. The identity matrix of order n is denoted by In (or simply I). An a × b matrix whose entries are all ones is denoted by Ja,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`. If M is the 0 − 1 incidence matrix of G, then M tM = A(G`) + 2I . Moreover, if G is k-regular, then MM t = A(G) + kI . Since the eigenvalues of any n×n symmetric matrix S are real, we denote and ordered the eigenvalues of S as follows: λmax(S) = λ1(S) ≥ λ2(S) ≥ · · · ≥ λn(S) = λmin(S). (2.1) For a graph G, sometimes we denote and arrange the eigenvalues of A(G), L(G) and Q(G) as ρ1(G) ≥ ρ2(G) ≥ · · · ≥ ρn(G), µ1(G) ≥ µ2(G) ≥ · · · ≥ µn(G) and q1(G) ≥ q2(G) ≥ · · · ≥ qn(G), respectively. Next, we present the well known Weyl Theorem. Theorem 2.2 ([17, Theorem 4.3.1]). If S1 and S2 are two Hermitian matrices of order n and their eigenvalues are ordered as in (2.1). Then λn+1−i(S1 + S2) ≤ λn+1−i−j(S1) + λj+1(S2), i = 1, 2, . . . , n; j = 0, 1, . . . , n− i. Corollary 2.3. If S1 and S2 are two Hermitian matrices of order n and their eigenvalues are ordered as in (2.1). Then λn(S1) + λ1(S2) ≤ λ1(S1 + S2) ≤ λ1(S1) + λ1(S2). 4 Ars Math. Contemp. 24 (2024) #P4.10 Let us recall the following upper bound of the largest eigenvalue of a Laplacian matrix. Theorem 2.4 ([6]). Let G be a graph with the largest Laplacian eigenvalue µ1(G). Then µ1(G) ≤ max vivj∈E(G) (di + dj). Let S = ( S11 S12 S21 S22 ) be a 2 × 2 block matrix, where S11 and S22 are square matrices. If S11 is nonsingular, then the Schur complement of S11 in S is defined to be the following matrix S22 − S21S−111 S12. (2.2) Similarly, if S22 is nonsingular, then the Schur complement of S22 in S is S11 − S12S −1 22 S21. Let us recall the Schur complement formula for the determinant. Theorem 2.5 ([2]). Let S = ( S11 S12 S21 S22 ) be a 2× 2 block matrix, where S11 and S22 are square matrices and S11 is nonsingular. Then detS = (detS11) det(S22 − S21S−111 S12). 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 = (sij)n×m be a matrix, then we denote |S| := (|sij |)n×m. Theorem 2.6 ([17, 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.7 ([17, 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α(G) Let G be a graph with Bα-matrix Bα(G) := αA(G) + (1 − α)L(G). In this section we determine the values of α for which the matrix Bα(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α, A, L, and D instead of Bα(G), A(G), L(G), and D(G), respectively, when G is clear from the context. Some equivalent forms of Bα in terms of A, L, and D are as follows: Bα = αA+ (1− α)L = (2α− 1)A+ (1− α)D = (1− 2α)L+ αD. Given two real matrices S = (sij)m×n and M = (mij)m×n, we use the notation S ≥M if and only if sij ≥ mij for all i, j. For any connected graph G with n vertices and A. Samanta et al.: Unifying adjacency, Laplacian, and signless Laplacian theories 5 α (6= 12 ) ∈ [0, 1], we have (I + |Bα|)n−1 = (I + |(2α− 1)A+ (1− α)D|)n−1 = (I + |2α− 1|A+ (1− α)D)n−1 ≥ I + |2α− 1|A+ · · ·+ |2α− 1|n−1An−1. (3.1) SinceG is connected, any two vertices vi and vj are joined by a path with length k ≤ n−1. Therefore (i, j)-th entry of Ak, which counts the number of walks of length k connecting vi and vj , is positive. Hence, from (3.1), (I + |Bα|)n−1 ≥ I + |2α − 1|A + · · · + |2α − 1|n−1An−1 > 0. Thus, by Theorem 2.6, Bα is irreducible for α (6= 12 ) ∈ [0, 1]. We begin the section with the following basic property of Bα(G). Proposition 3.1. For any α ∈ [0, 1], eigenvalues of Bα(G) are real numbers. Proof. SinceA(G) and L(G) are symmetric matrices, soBα(G) = αA(G)+(1−α)L(G) is also a symmetric matrix. Hence, all the eigenvalues of Bα are real numbers for any α ∈ [0, 1]. For a graph G, let λ1(Bα) ≥ · · · ≥ λn(Bα) be the eigenvalues of Bα(G). In the following theorem, we prove that λk(Bα) is uniformly continuous for α ∈ [0, 1]. Theorem 3.2. Let Bα be the Bα-matrix of a graph G with n vertices. Then, for k ∈ {1, 2, . . . , n}, the mapping fG : [0, 1] → R defined as fG(α) = λk(Bα) is a uniformly continuous function. Proof. Let L and D be the Laplacian and the degree matrix of G, respectively. Then, for any α, β ∈ [0, 1], we have Bα − Bβ = 2(β − α)L + (α − β)D. Then, for any i ∈ {1, 2, . . . , n} and j ∈ {0, 1, . . . , n− i}, using Theorem 2.2, we obtain λn+1−i(Bα) = λn+1−i(Bα +Bβ −Bβ) ≤ λn+1−i−j(Bα +Bβ) + λj+1(−Bβ) = λn+1−i−j(Bα +Bβ)− λn−j(Bβ). Thus, for any i ∈ {1, 2, . . . , n} and j ∈ {0, 1, . . . , n− i}, λn+1−i(Bα) + λn−j(Bβ) ≤ λn+1−i−j(Bα +Bβ) for all α, β ∈ [0, 1]. (3.2) Assume that α ≤ β. By using (3.2) and Corollary 2.3, we compute λk(Bα)− λk(Bβ) = λn+1−k(−Bβ) + λn−(n−k)(Bα) ≤ λn+1−k−(n−k)(−Bβ +Bα) = λ1(Bα −Bβ) ≤ λ1(2(β − α)L) + λ1((α− β)D) = 2(β − α)λ1(L) + (α− β)λn(D) ≤ |α− β|(2λ1(L) + λ1(D)). 6 Ars Math. Contemp. 24 (2024) #P4.10 Also, by using (3.2) and Corollary 2.3, we obtain λk(Bβ)− λk(Bα) ≤ λ1(Bβ −Bα) ≤ λ1(2(α− β)L) + λ1((β − α)D) = 2(α− β)λn(L) + (β − α)λ1(D) ≤ |α− β|(2λ1(L) + λ1(D)). Thus, |λk(Bβ)−λk(Bα)| ≤ |α−β|(2λ1(L)+λ1(D)). Hence, the mapping fG is uniformly continuous. Note that for a graph G (with at least an edge) on n vertices, λn(B 1 2 ) = 12λn(D) ≥ 0 and λn(B1) = λn(A) ≤ 0. By Theorem 3.2, λn(Bα) is continuous, so there exists a β ∈ (0, 1) such that λn(Bβ) = 0. Therefore, for a graph G (with at least an edge) on n vertices, we define βo(G) := max{β ∈ (0, 1) : λn(Bβ) = 0}. It is simply denoted by βo if the graph G is understood from the context. Theorem 3.3. If G is a connected graph with n (> 1) vertices, then Bα is positive definite for α ∈ (0, 23 ). Proof. First we assume that 0 < α ≤ 12 . SinceG is connected and λn(Bα) = −λ1(−Bα), by Corollary 2.3, we obtain λn(Bα) = λn((1− 2α)L+ αD) ≥ (1− 2α)λn(L) + αλn(D) = αλn(D) > 0. Thus, Bα is positive definite for α ∈ (0, 12 ]. Next we assume that 12 < α < 2 3 . Then 0 < 2α − 1 < 1 − α. Now Bα = (2α − 1)A + (1− α)D. Let (Bα)ij be the (i, j)-th entry of Bα. Then, for i ∈ {1, 2, . . . , n}, we have |(Bα)ii| = |(1− α) di| = (1− α) di > (2α− 1) di = |2α− 1| di = n∑ j=1, j 6=i |(Bα)ij |. Thus, Bα is strictly diagonally dominant with positive diagonal entries. Also, Bα is irre- ducible. Therefore, by Theorem 2.7, Bα is positive definite for α ∈ ( 12 , 2 3 ). Corollary 3.4. If G is a graph with no isolated vertices, then Bα is positive definite for α ∈ (0, 23 ). Next corollary gives a lower bound of βo(G). For simplicity, we use βo instead of βo(G). Corollary 3.5. If G is a graph with no isolated vertices, then βo ≥ 23 . Proof. By Theorem 3.2, fG(α) := λn(Bα) is continuous. By Corollary 3.4, λn(Bα) > 0 for α ∈ (0, 23 ). Also, λn(B1) < 0. Therefore, βo ≥ 2 3 . Theorem 3.6. Let G be a graph with no isolated vertices. Then Bα is positive semidefinite if and only if α ∈ [0, βo]. A. Samanta et al.: Unifying adjacency, Laplacian, and signless Laplacian theories 7 Proof. Let G be a graph with n vertices {v1, v2, . . . , vn}. Set βo := βo(G). Suppose α ∈ [0, βo]. For α ∈ (0, 23 ), by Corollary 3.4, Bα is positive definite. Assume that 2 3 ≤ α ≤ βo. Then −α ≥ −βo, that is, α (2βo − 1) ≥ βo (2α − 1) which implies α 2α−1 ≥ βo 2βo−1 . Note that for any x = (x1, x2, . . . , xn) t ∈ Rn, we obtain xtBα x = x t αD x + xt (1− 2α)Lx = α n∑ i=1 di x 2 i + (1− 2α) ∑ vjvi∈E(G) (xi − xj)2. (3.3) Then, for any x = (x1, x2, . . . , xn)t ∈ Rn and using (3.3), we obtain 0 ≤ xtBβox = βo n∑ i=1 di x 2 i + (1− 2βo) ∑ vjvi∈E(G) (xi − xj)2 which implies ∑ vjvi∈E(G) (xi − xj)2 ≤ βo 2βo − 1 n∑ i=1 di x 2 i ≤ α 2α− 1 n∑ i=1 di x 2 i . Thus, xtBαx = α n∑ i=1 di x 2 i + (1− 2α) ∑ vjvi∈E(G) (xi − xj)2 ≥ 0 for any x ∈ Rn. Hence, λn(Bα) = min{xtBαx : x ∈ Rn, ‖x‖ = 1} ≥ 0. Therefore, Bα is positive semidefinite for all α ∈ [0, βo]. To prove the converse, it is enough to prove that if α ∈ (βo, 1], then Bα is not positive semidefinite. Suppose there exists an α ∈ (βo, 1] such that λn(Bα) ≥ 0. By Theorem 3.2, the function fG(α) := λn(Bα) is continuous and λn(B1) < 0, so there exist a β ∈ [α, 1) such that λn(Bβ) = 0. This contradicts that βo is the largest number in (0, 1) for which λn(Bβo) = 0. Hence, λn(Bα) < 0 for all α ∈ (βo, 1]. A symmetric matrix M is called indefinite if there exist two nonzero vectors x and y such that yTMy > 0 > xTMx, where xT denotes the transpose of x. Corollary 3.7. For a graph G with no isolated vertices, Bα is indefinite if and only if α ∈ (βo, 1]. Proof. First we assume that Bα is indefinite. Set βo := βo(G). Then λ1(Bα) > 0 and λn(Bα) < 0. Thus, α ∈ (βo, 1]. Conversely, suppose α ∈ (βo, 1]. Then λn(Bα) < 0. Also, α > βo > 12 . Hence, by Corollary 2.3, we have λ1(Bα) = λ1((2α− 1)A+ (1− α)D) ≥ λ1((2α− 1)A) + λn((1− α)D) = (2α− 1)λ1(A) + (1− α)λn(D) > 0. Hence, Bα is indefinite. 8 Ars Math. Contemp. 24 (2024) #P4.10 In the next theorem, we find βo for regular graphs. Theorem 3.8. If G is an r-regular graph with smallest adjacency eigenvalue ρn(G). Then βo(G) = r − ρn(G) r − 2ρn(G) . Proof. Set βo := βo(G). Then 0 = λn(Bβo) = λn ( (2βo − 1)A+ (1− βo)D ) = λn ( (2βo − 1)A+ (1− βo)rI ) = (2βo − 1)λn(A) + (1− βo)r. This gives βo = r − λn(A) r − 2λn(A) . Let us recall the following Hoffman bound of independence number α(G) of an r- regular graph G with n vertices in terms of ρn(G). α(G) ≤ − ρn(G) r − ρn(G) n. In light of the above result, we obtain a close relation between the independence number α(G) of a regular graph G and βo(G). Proposition 3.9. Let G be an r-regular graph of n vertices with independence number α(G) and βo := βo(G). Then α(G) ≤ n ( 1− βo βo ) . 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α-matrix, we first show a partial Perron-Frobenius type result (that is, λ1(Bα) is the spectral radius of Bα). Then we compute the eigenvalues of Bα(G) for complete graph and complete bipartite graph. Thereafter, we obtain some lower and upper bounds on the largest eigenvalue of Bα(G) of graph G in terms of ∆ and δ. As a consequence, we deduce some known results. In addition, we establish an upper bound on the smallest eigenvalue of Bα(G) in terms of the chromatic number. Finally, we derive a bound on the chromatic number in terms of βo(G). It is to be observed that Bα-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α-matrix is the same as its largest eigenvalue. Theorem 4.1. For any α ∈ [0, 1], the spectral radius of Bα of a connected graph G is λ1(Bα). Proof. For α ∈ [0, 12 ], Bα is positive semidefinite by Theorem 3.3. Hence, λ1(Bα) is the spectral radius of Bα. Let α ∈ ( 12 , 1]. Then 2α−1 > 0 and henceBα = (2α−1)A+(1− α)D is a non-negative matrix. Also, Bα is irreducible. Therefore, by Perron-Frobenius Theorem, λ1(Bα) is the spectral radius of Bα. A. Samanta et al.: Unifying adjacency, Laplacian, and signless Laplacian theories 9 4.1 The spectrum of Bα-matrix for complete and complete bipartite graphs In this subsection, we determine the eigenvalues of Bα-matrices of the complete graph and the complete bipartite graph. Proposition 4.2. If G is a complete graph with n vertices, then eigenvalues of Bα(G) are (1− α)n− α with multiplicity n− 1 and (n− 1)α with multiplicity 1. A complete bipartite graph with vertex partition size a and b is denoted by Ka,b. Since the eigenvalues of the adjacency matrix of a complete bipartite graph are known, so we compute the eigenvalues of Bα(Ka,b) for α ∈ [0, 1). Proposition 4.3. For α ∈ [0, 1), the eigenvalues ofBα(Ka,b) are (1−α)a with multiplicity b− 1, (1− α)b with multiplicity a− 1, and (1− α)(a+ b)± √ (1− α)2(a− b)2 + 4(2α− 1)2ab 2 . Proof. Let Ja,b and Jb,a be the square matrices of order a × b and b × a, respectively, of all ones. Then Bα(Ka,b) = Bα = (2α− 1)A+ (1− α)D = (2α− 1) ( 0 Ja,b Jb,a 0 ) + (1− α) ( bIa 0 0 aIb ) = ( (1− α)bIa (2α− 1)Ja,b (2α− 1)Jb,a (1− α)aIb ) . For i ∈ {2, 3, . . . , a}, let the vector x(i) = (xi1, xi2, . . . , xia+b)t of order a+ b be defined as xij =  1 for j = 1, −1 for j = i, 0 otherwise. Then {x(2),x(3), . . . ,x(a)} is a linearly independent set of eigenvectors corresponding to the eigenvalue (1− α)b. Thus, Bα has eigenvalue (1− α)b with multiplicity a− 1. For i ∈ {a + 2, a + 3, . . . , a + b}, let the vector x(i) = (xi1, xi2, . . . , xia+b)t of order a+ b be defined as xij =  1 for j = a+ 1, −1 for j = i, 0 otherwise. Then {x(a+2),x(a+3), . . . ,x(a+b)} is a linearly independent set of eigenvectors corre- sponding to the eigenvalue (1− α)a. Thus, Bα has eigenvalue (1− α)a with multiplicity b− 1. 10 Ars Math. Contemp. 24 (2024) #P4.10 Let α ∈ [0, 1). Then, by using Theorem 2.5, we compute det(Bα) = ∣∣∣∣∣ (1− α) b Ia (2α− 1) Ja,b(2α− 1) Jb,a (1− α) a Ib ∣∣∣∣∣ = det ( (1− α) b Ia ) det ( (1− α)a Ib − (2α− 1) Jb,a ( (1− α) b Ia )−1 (2α− 1) Ja,b ) = (1− α)a ba det ( (1− α)aIb − (2α− 1)2Jb,a 1 (1− α)b IaJa,b ) = (1− α)a ba det ( (1− α)aIb − a(2α− 1)2 (1− α)b Jb,b ) = (1− α)a ba(1− α)b−1 ab−1 ( (1− α) a− a (2α− 1) 2 (1− α) ) . Let x and y be the remaining eigenvalues of Bα(Ka,b). Then xy ( (1− α) a )b−1( (1− α) b )a−1 = = (1− α)a ba (1− α)b−1 ab−1 ( (1− α) a− a (2α− 1) 2 (1− α) ) . Thus we obtain xy = b(1− α) ( (1− α)a− a(2α− 1) 2 (1− α) ) = (1− α)2ab− (2α− 1)2ab. (4.1) Since the sum of the eigenvalues is equal to the trace of the matrix, we obtain x+ y + (b− 1)(1− α)a+ (a− 1)(1− α)b = (1− α)ab+ (1− α)ab, that is, x = (1− α)(a+ b)− y. Substitute the value of x in (4.1), we obtain y2 − (1− α)(a+ b)y + (1− α)2ab− (2α− 1)2ab = 0. This gives y = (1− α)(a+ b)± √ (1− α)2(a− b)2 + 4(2α− 1)2ab 2 . Hence the eigenvalues of Bα(Ka,b) are (1 − α)a with multiplicity b − 1, (1 − α)b with multiplicity a− 1 and (1− α)(a+ b)± √ (1− α)2(a− b)2 + 4(2α− 1)2ab 2 . A. Samanta et al.: Unifying adjacency, Laplacian, and signless Laplacian theories 11 4.2 Bounds on the largest eigenvalue For a connected graph G with vertex set V (G) = {v1, v2, . . . , vn}, the distance between two vertices vi and vj is denoted by d(vi, vj) and is defined to be the length of the short- est path between them. We now establish some lower and upper bounds on the largest eigenvalue of Bα(G) of graph G. Theorem 4.4. Let G be a connected graph with the minimum degree δ. Then, for any α ∈ [0, 1] λ1(Bα) ≥ αδ. Proof. First we assume that α ∈ [0, 12 ], that is, 2α − 1 ≤ 0. Let x = (x1, x2, . . . , xn) t ∈ Rn be an eigenvector of Bα corresponding to λ1(Bα) such that xk = min 1≤i≤n xi < 0. Then λ1(Bα)xk = (2α− 1) ∑ vj :vkvj∈E(G) xj + (1− α)dkxk ≤ (2α− 1) dkxk + (1− α)dk xk = αdkxk. Therefore, λ1(Bα) ≥ αdk ≥ αδ. Next we assume that α ∈ ( 12 , 1], that is, 2α − 1 > 0. Then Bα is irreducible and non-negative. Therefore, by Perron-Frobenius Theorem, Bα has a Perron eigenvector x = (x1, x2, . . . , xn) t > 0 corresponding to the eigenvalue λ1(Bα). Let xk = min 1≤i≤n xi > 0. Then we have λ1(Bα)xk = (2α− 1) ∑ vj :vjvk∈E(G) xj + (1− α)dkxk ≥ (2α− 1)dkxk + (1− α)dkxk = αdkxk. Thus, λ1(Bα) ≥ αdk ≥ αδ, for α ∈ ( 12 , 1]. Hence, λ1(Bα) ≥ αδ for all α ∈ [0, 1]. Let NG(v1) denote the set of vertices of G which are adjacent to v1. Let NG[v1] := NG(v1) ∪ {v1}. Theorem 4.5. Let G be a graph with at least one edge and maximum degree ∆. Then, for any α ( 6= 12 ) ∈ [0, 1], λ1(Bα) ≥ Y Z , where Y and Z are given by Y = [ α2 (3α− 1)2 (∆ + 1)2 ( 2αm2 + (1− α)m3 ) + (1− α) (2α− 1)2 × (2∆ + 5α− 3α2)2 ∆ ] P 2 + 4 (2α− 1)2 (∆ + 1) [ (2α− 1) ∆ (2∆ + 5α− 3α2) + α (3α− 1) (∆ + 1)m3 ] PQ+ 4 (2α− 1)2 (∆ + 1)2 [ 2αm1 + (1− α) (∆ +m3) ] Q2, (4.2) 12 Ars Math. Contemp. 24 (2024) #P4.10 Z = [ (2α− 1)2 (2∆ + 5α− 3α2)2 + α2 (3α− 1)2 (∆ + 1)2 (n−∆− 1) ] P 2 + 4∆ (∆ + 1)2 (2α− 1)2Q2 (4.3) with P = (2α− 1) ( (α− 1) (3α− 2) ∆ + 2 ) and Q = 16α2 − 6α3 − 10α+ 2, (4.4) andm1 = |E(NG(v1))|, is the number of edges in the setNG(v1),m2 = |E(V (G)\NG[v1])|, is the number of edges in the set V (G)\NG[v1],m3 is the number of edges betweenNG(v1) and V (G)\NG[v1], and the vertex v1 has degree ∆. Proof. Let v1 be the maximum degree vertex of degree ∆ inG. Also let S = {v2, v3, . . . , v∆+1} be the set of vertices adjacent to v1 inG. Let x = (x1, x2, . . . , xn)t be any non-zero vector. Using Rayleigh quotient, we obtain xtBαx ≤ λ1(Bα)xtx, that is, λ1(Bα) ≥ 2α ∑ vivj∈E(G) xixj + (1− α) ∑ vivj∈E(G) (xi − xj)2 n∑ i=1 x2i . (4.5) We consider the following two cases: Case1. (α−1) (3α−2) ∆+2 6= 0. In this case P = (2α−1) ( (α−1) (3α−2) ∆+2 ) 6= 0 as α 6= 12 . Setting xi =  1− 2− 5α+ 3α 2 2(∆ + 1) for i = 1, 16α2 − 6α3 − 10α+ 2 (2α− 1) ( (α− 1) (3α− 2) ∆ + 2 ) for i = 2, 3, . . . ,∆ + 1, α(3α− 1) 2(2α− 1) Otherwise. (4.6) Since m1 = |E(NG(v1))|, m2 = |E(V (G)\NG[v1])|, and m3 is the number of edges between NG(v1) and V (G)\NG[v1], we obtain∑ vivj∈E(G) xixj = (2∆ + 5α− 3α2) (16α2 − 6α3 − 10α+ 2) 2(∆ + 1) (2α− 1) ( (α− 1) (3α− 2) ∆ + 2 ) ∆ + (16α2 − 6α3 − 10α+ 2)2 (2α− 1)2 ( (α− 1) (3α− 2) ∆ + 2 )2 m1 + α2 (3α− 1)24 (2α− 1)2 m2 + α(3α− 1) (16α2 − 6α3 − 10α+ 2) 2(2α− 1)2 ( (α− 1) (3α− 2) ∆ + 2 ) m3, A. Samanta et al.: Unifying adjacency, Laplacian, and signless Laplacian theories 13 ∑ vivj∈E(G) (xi − xj)2 =  (2∆ + 5α− 3α2) 2(∆ + 1) − 16α 2 − 6α3 − 10α+ 2 (2α− 1) ( (α− 1) (3α− 2) ∆ + 2 ) 2 ∆ +  16α2 − 6α3 − 10α+ 2 (2α− 1) ( (α− 1) (3α− 2) ∆ + 2 ) − α(3α− 1) 2(2α− 1) 2 m3, and n∑ i=1 x2i = (2∆ + 5α− 3α2)2 4(∆ + 1)2 + (16α2 − 6α3 − 10α+ 2)2 (2α− 1)2 ( (α− 1) (3α− 2) ∆ + 2 )2 ∆ + α2(3α− 1)2 4(2α− 1)2 (n−∆− 1). Using the above results in (4.5), we obtain λ1(Bα) ≥ Y Z as 2α ∑ vivj∈E(G) xixj + (1− α) ∑ vivj∈E(G) (xi − xj)2 = Y 4 (2α− 1)2 (∆ + 1)2 P 2 and n∑ i=1 x2i = Z 4 (2α− 1)2 (∆ + 1)2 P 2 , where Y , Z and P are given by (4.2), (4.3) and (4.4), respectively. Moreover, the equality holds if and only if x = (x1, x2, . . . , xn)t is an eigenvector corresponding to the eigenvalue λ1(Bα) of Bα, where xi is given in (4.6). Case2. (α−1) (3α−2) ∆+2 = 0. In this case P = (2α−1) ( (α−1) (3α−2) ∆+2 ) = 0. Thus we obtain Y = 4 (2α−1)2 (∆+1)2 [ 2αm1+(1−α) (∆+m3) ] Q2 and Z = 4∆ (∆+1)2 (2α−1)2Q2. Setting xi =  0 for i = 1, 1 for i = 2, 3, . . . ,∆ + 1, 0 Otherwise. Since m1 = |E(NG(v1))|, m2 = |E(V (G)\NG[v1])|, and m3 is the number of edges between NG(v1) and V (G)\NG[v1], we obtain∑ vivj∈E(G) xixj = m1, ∑ vivj∈E(G) (xi − xj)2 = ∆ +m3 and n∑ i=1 x2i = ∆. 14 Ars Math. Contemp. 24 (2024) #P4.10 Using the above results in (4.5), we obtain λ1(Bα) ≥ 2αm1 + (1− α) (∆ +m3) ∆ = Y Z . Moreover, the equality holds if and only if x = (0, 1, . . . , 1︸ ︷︷ ︸ ∆ , 0, . . . , 0︸ ︷︷ ︸ n−∆−1 )t is an eigenvector corresponding to the eigenvalue λ1(Bα) of Bα. Corollary 4.6. Let G be a graph of order n with m edges and maximum degree ∆. Then ρ1(G) ≥ 2m n with equality if and only if G is a regular graph. Proof. For adjacency matrix, α = 1, that is, B1 = B1(G) = A(G). For α = 1, from Theorem 4.5, we obtain P = 2 = Q, Y = 32 (∆+1)2 (∆+m1+m2+m3) = 32 (∆+1) 2m and Z = 16 (∆+1)2 n and hence ρ1(G) = λ1(B1) ≥ Y Z = 2m n . Moreover, the equality holds if and only if x = (1, 1, . . . , 1)t is an eigenvector corre- sponding to the eigenvalue λ1(B1) (= ρ1(G)) of B1, that is, if and only if G is a regular graph. Corollary 4.7. Let G be a graph of order n with m edges and maximum degree ∆. Then µ1(G) ≥ ∆ + 1. If G is connected, then the above equality holds if and only if ∆ = n− 1. Proof. For Laplacian matrix, α = 0, that is, B0 = B0(G) = L(G). For α = 0, from Theorem 4.5, we obtain P = −2 (∆+1), Q = 2, Y = 16 ∆(∆+1)2 ( (∆+1)2 + m3 ∆ ) and Z = 16 ∆ (∆+1)3. and hence µ1(G) = λ1(B0) ≥ Y Z = ∆ + 1 + m3 ∆ (∆ + 1) ≥ ∆ + 1 as m3 ≥ 0. Suppose that G is connected. Then the equality holds if and only if x =  ∆∆ + 1 ,− 1∆ + 1 , . . . ,− 1∆ + 1︸ ︷︷ ︸ ∆ , 0, . . . , 0︸ ︷︷ ︸ n−∆−1  t is an eigenvector corresponding to the eigenvalue λ1(B0) (= µ1(G)) of B0 and m3 = 0. Since G is connected, then ∆ = n− 1. If ∆ = n− 1, then one can easily see that µ1(G) = n = ∆ + 1. This completes the proof of the result. A. Samanta et al.: Unifying adjacency, Laplacian, and signless Laplacian theories 15 Corollary 4.8. Let G be a graph of order n with m edges and maximum degree ∆. Then q1(G) ≥ 4m n with equality if and only if G is a regular graph. Proof. For signless Laplacian matrix, α = 23 , that is, B2/3 = B2/3(G) = 1 3 Q(G). For α = 23 , from Theorem 4.5, we obtain P = 2 3 = Q, Y = 64 243 (∆+1)2 (∆+m1+m2+m3) = 64 243 (∆+1)2m, Z = 16 81 (∆+1)2 n and hence 1 3 q1(G) = λ1(B2/3) ≥ Y Z = 4m 3n , that is, q1(G) ≥ 4m n . Moreover, the equality holds if and only if x = (1, 1, . . . , 1)t is an eigenvector correspond- ing to the eigenvalue λ1(B2/3) (= 13 q1(G)) of B2/3, that is, if and only if G is a regular graph. The lower bounds found in Corollaries 4.6-4.8 are classical. One can find all of them in [26]. Remark 4.9. In the following Table, we give a comparison between the exact value of λ1(Bα) (Proposition 4.3) and the lower bound on λ1(Bα) obtained in Theorem 4.5 for the graph G = K1,24. α Exact value of λ1(Bα) YZ 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 λ1(Bα) and YZ . Next, we observe that the following upper bound is continuous on α. Theorem 4.10. Let G be a connected graph with maximum degree ∆. Then, for any α ∈ [0, 1], λ1 (Bα) ≤ (2− 3α) ∆ if α ∈ [0, 1 2 ], α∆ if α ∈ ( 12 , 1]. 16 Ars Math. Contemp. 24 (2024) #P4.10 Proof. First we assume that α ∈ [0, 12 ]. Then, by using α ≥ 0, (1−2α) ≥ 0, Corollary 2.3, and Theorem 2.4, we have λ1(Bα) = λ1 ( αD + (1− 2α)L ) ≤ λ1(αD) + λ1 ( (1− 2α)L ) ≤ α∆ + (1− 2α)(2∆). That is, λ1(Bα) ≤ (2− 3α)∆ for all α ∈ [0, 12 ]. Next we assume that α ∈ ( 12 , 1]. That is, 2α− 1 > 0. Let x = (x1, x2, . . . , xn) t be an eigenvector of Bα corresponding to the eigenvalue λ1(Bα) such that xk = max 1≤i≤n xi > 0. Then we obtain λ1(Bα)xk = (2α− 1) ∑ vj :vjvk∈E(G) xj + (1− α) dk xk ≤ (2α− 1) dk xk + (1− α) dk xk = αdk xk ≤ α∆xk. Therefore, λ1(Bα) ≤ α∆ for all α ∈ ( 12 , 1]. For α ∈ [0, 1] and non-negative integers a and b, define fα(a, b) = (1− α) (a+ b) + √ (1− α)2 (a− b)2 + 4(2α− 1)2 ab 2 . Theorem 4.11. Let G = (U, W, E) be a connected bipartite graph, where |U | = a, |W | = b. For α ∈ [0, 1], λ1(Bα) ≤ fα(a, b) (4.7) with equality if and only if G ∼= Ka,b. Proof. Without loss of generality, assume that a ≥ b. Now, from Proposition 4.3, we have fα(a, b) = λ1(Bα(Ka,b)). Since, by definition, B0 = B0(G) = L(G) and G ⊆ Ka,b, by (edge) interlacing and Proposition 4.3, λ1(B0) = µ1(G) ≤ a+ b = f0(a, b). Since B 1 2 = B 1 2 (G) = 12 D(G), we have λ1(B 1 2 ) = 1 2 ∆(G) ≤ 1 2 ∆(Ka,b) = 1 2 a = f 1 2 (a, b). As B1 = B1(G) = A(G), by (vertex) interlacing and Proposition 4.3, we have λ1(B1) = ρ1(G) ≤ ρ1(Ka,b) = f1(a, b). So we have to prove the result in (4.7) for 0 < α < 12 and 1 2 < α < 1. Let x = (x1, x2, . . . , xn) T be an eigenvector corresponding to the largest eigenvalue λ1(Bα) of Bα. Then Bαx = λ1(Bα)x. We consider two cases: Case1. 12 < α < 1. Let xi = max1≤k≤n xk. Without loss of generality, we can assume that vi ∈ U . Let xj = max vk∈W xk. For vi ∈ U , we obtain λ1(Bα)xi = (1− α) dixi + (2α− 1) ∑ vk:vivk∈E(G) xk ≤ (1− α) dixi + (2α− 1) dixj , A. Samanta et al.: Unifying adjacency, Laplacian, and signless Laplacian theories 17 that is, [ λ1(Bα)− (1− α) di ] xi ≤ (2α− 1) dixj . (4.8) Similarly, for vj ∈W , we obtain[ λ1(Bα)− (1− α) dj ] xj ≤ (2α− 1) djxi. (4.9) From the above two results, we obtain[ λ1(Bα)−(1− α) b ] [ λ1(Bα)− (1− α) a ] ≤ ≤ [ λ1(Bα)− (1− α) di ] [ λ1(Bα)− (1− α) dj ] ≤(2α− 1)2 di dj ≤ (2α− 1)2 ab. (4.10) Thus we obtain λ1(Bα) 2 − (1− α) (a+ b)λ1(Bα) + (1− α)2 ab− (2α− 1)2 ab ≤ 0, that is, λ1(Bα) ≤ (1− α) (a+ b) + √ (1− α)2 (a− b)2 + 4(2α− 1)2 ab 2 = fα(a, b). The first part of the proof is done. Suppose that equality holds. Then all inequalities in the above argument must be equal- ities. From equalities in (4.8) and (4.9), we obtain xk = xi for all vk ∈ NG(vj) ⊆ U and x` = xj for all v` ∈ NG(vi) ⊆ W . From equality in (4.10), we obtain di = b and dj = a. Since G is a connected bipartite graph, one can easily prove that xk = xi for all vk ∈ U and x` = xj for all v` ∈W . For vi, vk ∈ U , we have λ1(Bα)xi = (1− α) dixi + (2α− 1) ∑ vk:vivk∈E(G) xk = b [ (1− α)xi + (2α− 1)xj ] and λ1(Bα)xi = dk [ (1− α)xi + (2α− 1)xj ] . Thus we have b [ (1− α)xi + (2α− 1)xj ] = dk [ (1− α)xi + (2α− 1)xj ] , that is, ( b− dk ) [ (1− α)xi + (2α− 1)xj ] = 0. Since all the elements in Bα are non-negative, by Perron-Frobenius theorem in matrix theory, we obtain that all the eigencomponents corresponding to the spectral radius λ1(Bα) are non-negative. SinceG is connected, xi ≥ xj > 0. From the above with 12 < α < 1, we must have dk = b for any vk ∈ U . Similarly, d` = a for any v` ∈W . Hence G ∼= Ka,b. Case2. 0 < α < 12 . Let xi = max1≤k≤n xk. Without loss of generality, we can assume that vi ∈ U . Let xj = minvk:vivk∈E(G) xk. For vi ∈ U , we obtain λ1(Bα)xi = (1− α) dixi + (2α− 1) ∑ vk:vivk∈E(G) xk ≤ (1− α) dixi + (2α− 1) dixj , 18 Ars Math. Contemp. 24 (2024) #P4.10 that is, [ λ1(Bα)− (1− α) di ] xi ≤ (2α− 1) dixj . Similarly, for vj ∈W , we obtain[ λ1(Bα)− (1− α) dj ] xj ≥ (2α− 1) djxi. Since α < 12 , from the above two results, we obtain[ λ1(Bα)− (1− α) di ] [ λ1(Bα)− (1− α) dj ] xi ≤(2α− 1) di [ λ1(Bα)− (1− α) dj ] xj ≤(2α− 1)2 di dj xi, that is, [ λ1(Bα)− (1− α) di ] [ λ1(Bα)− (1− α) dj ] ≤ (2α− 1)2 di dj , that is, [ λ1(Bα)− (1− α) b ] [ λ1(Bα)− (1− α) a ] ≤ (2α− 1)2 ab. Thus we obtain λ1(Bα) 2 − (1− α) (a+ b)λ1(Bα) + (1− α)2 ab− (2α− 1)2 ab ≤ 0, that is, λ1(Bα) ≤ (1− α) (a+ b) + √ (1− α)2 (a− b)2 + 4(2α− 1)2 ab 2 = fα(a, b). Suppose that equality holds. Similarly as Case1, one can easily prove that G ∼= Ka,b. Conversely, let G ∼= Ka,b. By Proposition 4.3, we obtain λ1(Bα) = (1− α) (a+ b) + √ (1− α)2 (a− b)2 + 4(2α− 1)2 ab 2 = fα(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α-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.12. Let G be a graph of n vertices, m (> 0) edges and chromatic number χ. Then, for any α ∈ [0, 1], λn (Bα) ≤ 2m n ( χ (1− α)− α χ− 1 ) . (4.11) A. Samanta et al.: Unifying adjacency, Laplacian, and signless Laplacian theories 19 Proof. Set Bα := Bα(G). Partition the vertex set V (G) as χ number of subsets V1, V2, . . . , Vχ, where each subset contains the vertices having the same colour. For each j ∈ {1, 2, . . . , χ}, define a vector x := (x1, x2, . . . , xn)t as follows: xi = { χ− 1 for vi ∈ Vj −1 otherwise. Then ||x|| 2 = n∑ i=1 x2i = (χ− 1)2 |Vj |+ (n− |Vj |) = χ (χ− 2) |Vj |+ n. For j ∈ {1, 2, . . . , χ}, define mj = ∑ v∈Vj d(v). Now, 〈Bαx, x〉 = 〈(2α− 1)Ax, x〉+ 〈(1− α)Dx, x〉. Note that 〈Ax, x〉 = 2 ∑ vivj∈E(G) xi xj = 2 (1− χ)mj + 2 (m−mj) and 〈Dx, x〉 = ∑ vi∈V di x 2 i = (χ− 1)2mj + (2m−mj) = χ (χ− 2)mj + 2m. Thus we obtain 〈Bαx, x〉 = (2α− 1) 〈Ax, x〉+ (1− α) 〈Dx, x〉 = 2 (2α− 1) (1− χ)mj + 2 (2α− 1) (m−mj) + (1− α)χ (χ− 2)mj + 2 (1− α)m = 2mα+ ( χ− α (χ+ 2) ) χmj . Using Rayleigh quotient, we obtain λn (Bα) ||x||2 ≤ 〈Bαx, x〉. Therefore, by the above inequalities, we have λn(Bα) ( χ (χ− 2) |Vj |+ n ) ≤ 2mα+ ( χ− α (χ+ 2) ) χmj , that is, χ∑ j=1 λn(Bα) ( χ (χ− 2) |Vj |+ n ) ≤ χ∑ j=1 ( 2mα+ ( χ− α (χ+ 2) ) χmj ) , that is, λn(Bα) ( (χ2 − 2χ)n+ nχ ) ≤ 2χ2m− 2αχ2m− 2mχα. Therefore, λn (Bα) ≤ 2m n ( χ (1− α)− α χ− 1 ) . 20 Ars Math. Contemp. 24 (2024) #P4.10 In the next couple of results, we partially characterize the graphs attaining the equality in (4.11) of Theorem 4.12. The proofs technique is similar to the one used in [21]. Theorem 4.13. Let G be a bipartite graph of n vertices with m edges. Then, for any α ∈ [0, 1], λn(Bα) ≤ 2m n (2− 3α). (4.12) Equality occurs if and only if either α = 23 , or G is regular with α ≥ 1 2 . Proof. Set λn := λn(Bα). For any x = (x1, x2, . . . , xn)t ∈ Rn, by Rayleigh quotient, we obtain λn x t x ≤ xtBα x that is, λn n∑ i=1 x2i ≤ α n∑ i=1 di x 2 i +(1−2α) ∑ vivj∈E(G), i