Search

It is shown that the nilpotency of submatrices of a certain class of adjacency matrices is equivalent to the Collatz conjecture. Our main result extends the previous work of Alves et al. and clarifies a conjecture made by Cardon and Tuckfield. [ABSTRACT FROM AUTHOR]

In this paper, we develop a new approach to study the spectral properties of Boolean graphs using the zeta and Möbius functions on the Boolean algebra B n of order 2 n. This approach yields new proofs of the previously known results about the reciprocal eigenvalue property of Boolean graphs. Further, this approach allows us to extend the results to a more general setting of the zero-divisor graphs Γ (P) of complement-closed and convex subposets P of B n. To do this, we consider the left linear representation of the incidence algebra of a poset P on the vector space of all real-valued functions V (P) on P. We then write down the adjacency operator A of the graph Γ (P) as the composition of two linear operators on V (P) , namely, the operator that multiplies elements of V (P) on the left by the zeta function ζ of P and the complementation operator. This allows us to obtain the determinant of A and the inverse of A in terms of the Möbius function μ of the complement-closed posets P. Additionally, if we impose convexity on the poset P , then we obtain the strong reciprocal or strong anti-reciprocal eigenvalue property of Γ (P) and also obtain the absolute palindromicity of the characteristic polynomial of A. This produces a large family of examples of graphs having the strong reciprocal or strong anti-reciprocal eigenvalue property. [ABSTRACT FROM AUTHOR]

The (k , r) -fan, denoted by F k , r , is the graph consisting of k copies of the complete graph K r which intersect in a single vertex. Desai et al. [7] proved that E X s p (n , F k , r) ⊆ E X (n , F k , r) for sufficiently large n , where E X s p (n , F k , r) and E X (n , F k , r) are the sets of n -vertex F k , r -free graphs with maximum spectral radius and maximum size, respectively. In this paper, the set E X s p (n , F k , r) is uniquely determined for n large enough. Let H s , t 1 , ... , t k be the graph consisting of s triangles and k odd cycles of lengths t 1 , ... , t k ≥ 5 intersecting in exactly one common vertex, denoted by H s , k for short. Li and Peng [12] showed that E X s p (n , H s , k) ⊆ E X (n , H s , k) for n large enough. In this paper, the set E X s p (n , H s , k) is uniquely characterized for sufficiently large n. [ABSTRACT FROM AUTHOR]

Let G be a finite simple graph with λ as an eigenvalue (i.e. an eigenvalue of the adjacency matrix of G), and let H be a star complement for λ in G. Motivated by a controllability condition, we say that H is a strong star complement for λ if G and H have no eigenvalue in common. We explore this concept in the context of line graphs, exceptional graphs, strongly regular graphs and graphs with a prescribed star complement. [ABSTRACT FROM AUTHOR]

For a set of graphs F , a graph is said to be F -free if it does not contain any graph in F as a subgraph. Let Ex s p (n , F) denote the graphs with the maximum spectral radius among all F -free graphs of order n. A linear forest is a graph whose connected components are paths. Denote by L s the family of all linear forests with s edges. In this paper the graphs in Ex s p (n , { K k + 1 , L s }) will be completely characterized when n is appropriately large. [ABSTRACT FROM AUTHOR]

The spectral radius ρ (A) is the maximum absolute value of the eigenvalues of a matrix A. In this paper, we establish some relationship between the spectral radius of a symmetric matrix and its principal submatrices, i.e., if A is partitioned as a 2 × 2 block matrix A = ( 0 A 12 A 21 A 22 ) , then ρ (A) 2 ≤ ρ 2 2 + θ ⁎ , where θ ⁎ is the largest real root of the equation μ 2 = (x − ν) 2 (ρ 2 2 + x) and ρ 2 = ρ (A 22) , μ = ρ (A 12 A 22 A 21) , ν = ρ (A 12 A 21). Furthermore, the results are used to obtain several upper bounds of the spectral radius of graphs, which strengthen or improve some known results. [ABSTRACT FROM AUTHOR]

In this article we establish relationships between Leavitt path algebras, talented monoids and the adjacency matrices of the underlying graphs. We show that indeed the adjacency matrix generates in some sense the group action on the generators of the talented monoid. With the help of this, we deduce a form of the aperiodicity index of a graph via the talented monoid. We classify hereditary and saturated subsets via the adjacency matrix. This then translates to a correspondence between the composition series of the talented monoid and the so-called matrix composition series of the adjacency matrix. In addition, we discuss the number of cycles in a graph. In particular, we give an equivalent characterization of acyclic graphs via the adjacency matrix, the talented monoid and the Leavitt path algebra. Finally, we compute the number of linearly independent paths of certain length in the Leavitt path algebra via adjacency matrices. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the adjacency matrices of finite undirected simple graphs over a finite prime field F p. We apply symmetric (row and column) elementary transformations to the adjacency matrix over F p in order to get a direct sum decomposition by other adjacency matrices. In this paper, we give a complete description of the direct sum decomposition of the adjacency matrix of any graph over F p for any odd prime p. Our key tool is quadratic residues of F p. [ABSTRACT FROM AUTHOR]

In this paper, we provide a characterization of fractional revival between twin vertices in a weighted graph with respect to its adjacency, Laplacian and signless Laplacian matrices. As an application, we characterize fractional revival between apexes of double cones. [ABSTRACT FROM AUTHOR]

A graph G is divisible by a graph H if the characteristic polynomial of G is divisible by that of H. In this paper, a necessary and sufficient condition for recursive graphs to be divisible by a path is used to show that the H-shape graph P 2 , 2 ; n − 4 2 , n − 7 , known to be (for n large enough) the minimizer of the spectral radius among the graphs of order n and diameter n − 5 , is determined by its adjacency spectrum if and only if n ≠ 10 , 13 , 15. [ABSTRACT FROM AUTHOR]

For a set of graphs F , let ex (n , F) and spex (n , F) denote the maximum number of edges and the maximum spectral radius of an n -vertex F -free graph, respectively. Nikiforov (LAA , 2007) gave the spectral version of the Turán Theorem by showing that spex (n , K k + 1) = λ (T k (n)) , where T k (n) is the k -partite Turán graph on n vertices. In the same year, Feng, Yu and Zhang (LAA) determined the exact value of spex (n , M s + 1) , where M s + 1 is a matching with s + 1 edges. Recently, Alon and Frankl (arXiv:2210.15076) gave the exact value of ex (n , { K k + 1 , M s + 1 }). In this article, we give the spectral version of the result of Alon and Frankl by determining the exact value of spex (n , { K k + 1 , M s + 1 }) when n is large. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a finite undirected graph of order n and of size m. Let Δ and δ be the largest and the smallest degree of G , respectively. The spectral radius of G is the largest eigenvalue of the adjacency matrix of the graph G. In this note we give new bounds on the spectral radius of { C 3 , C 4 } -free graphs in terms of m , n , Δ and δ. Computer search shows that in most of the cases the bounds derived in this note are better than the existing bounds. [ABSTRACT FROM AUTHOR]

Let G be a graph of size m and ρ (G) be the spectral radius of its adjacency matrix. A graph is said to be F -free if it does not contain a subgraph isomorphic to F. Let θ 1 , 2 , 3 denote the graph obtained from three internally disjoint paths with the same pair of endpoints, where the three paths are of lengths 1, 2, 3, respectively. Recently, Li, Sun and Wei showed that for any θ 1 , 2 , 3 -free graph G of size m ≥ 8 , ρ (G) ≤ 1 + 4 m − 3 2 , with equality if and only if G ≅ S m + 3 2 , 2 , where S m + 3 2 , 2 = K 2 ▿ K m − 1 2 ‾. However, this bound is not attainable when m is even. In this paper, we characterize the graphs with the maximum spectral radius over K 2 , r + 1 -free non-star graphs with m ≥ (4 r + 2) 2 + 1 , the graphs with the maximum spectral radius over θ 1 , 2 , 3 -free graphs with m ≥ 22 when m is even, and the graphs with the second largest spectral radius over θ 1 , 2 , 3 -free graphs with m ≥ 22 when m is odd. [ABSTRACT FROM AUTHOR]

We characterize the simple connected graphs with the second largest eigenvalue less than 1/2, which consists of 13 classes of specific graphs. These 13 classes hint that c 2 ∈ [ 1 / 2 , 2 + 5 ] , where c 2 is the minimum real number c for which every real number greater than c is a limit point in the set of the second largest eigenvalues of the simple connected graphs. We leave it as a problem. [ABSTRACT FROM AUTHOR]

In this paper, we characterize all graphs with eigenvectors of the signless Laplacian and adjacency matrices with components equal to { − 1 , 0 , 1 }. We extend the graph parameter max k -cut to square matrices and prove a general sharp upper bound, which implies upper bounds on the max k -cut of a graph using the smallest signless Laplacian eigenvalue, the smallest adjacency eigenvalue, and the largest Laplacian eigenvalue of the graph. In addition, we construct infinite families of extremal graphs for the obtained upper bounds. [ABSTRACT FROM AUTHOR]

In this article, we consider the trees for which the adjacency matrix has nullity at most one. We study the smallest positive (adjacency) eigenvalue of these trees. For such trees lower bounds on the smallest positive eigenvalue have already been obtained in literature but the problem of finding an upper bound still remains unsolved. In this article, we find upper bounds on the smallest positive eigenvalue of these trees and obtain corresponding unique maximal trees. Additionally, we study the smallest positive eigenvalue of trees obtained by attaching a pendant at some vertex of a path graph and also identify the trees for the extremal cases. As applications of our earlier results, we show that, for a path of odd order, the smallest positive eigenvalue is maximum, if we add the pendant almost in the middle. As another application, we show that for a path of any order, the smallest positive eigenvalue is minimum, if we add the pendant vertex at the end. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n with domination number γ (G). Wang, Yan, Fang, Geng and Tian [Linear Algebra Appl. 607 (2020), 307-318] showed that for any Laplacian eigenvalue λ of G with multiplicity m G (λ) , it holds that γ (G) ≤ n − m G (λ). Using techniques from the theory of star sets, in this work we prove that the same bound holds when λ is an arbitrary adjacency eigenvalue of a non-regular graph, and we characterize the cases of equality. Moreover, we show a result that gives a relationship between start sets and the p -domination number, and we apply it to extend the aforementioned spectral bound to the p -domination number using the adjacency and Laplacian eigenvalue multiplicities. [ABSTRACT FROM AUTHOR]

In this article, we consider the generalization of the Laplacian matrix for hypergraphs to obtain several results related to spectral properties of hypergraphs. This generalization of Laplacian matrix was defined in 2021 by Anirban Banerjee. We first supply a necessary and sufficient condition on the Laplacian spectral radius of hypergraphs such that the complement of that hypergraph is connected. We give bounds for the Laplacian spectral radius of k -uniform hypergraphs in terms of some invariants of hypergraph, such as the maximum degree, minimum degree, first Zagreb index, and the chromatic number. As an application of these results, some upper bounds of the Nordhaus-Gaddum type are obtained for the sum of Laplacian spectral radius of a k -uniform hypegraphs and its complement, and product of Laplacian spectral radius of a k -uniform hypegraphs and its complement. It is known that the second largest Laplacian eigenvalue for graphs is greater or equal to the second highest degree of graphs. We show by an example that this result is not true for 3-uniform hypergraphs in general. Finally, we supply a class of 3-uniform hypergraphs for which the second largest Laplacian eigenvalue is greater or equal to the second highest degree. [ABSTRACT FROM AUTHOR]

Let D be a strongly connected digraph and α ∈ [ 0 , 1 ]. In Liu et al. (2019) [13] the matrix A α (D) = α D e g (D) + (1 − α) A (D) , where A (D) and D e g (D) are the adjacency matrix and the diagonal matrix of the out-degrees of D , respectively, was defined. In this paper it is established some sharp bounds on the A α (D) -spectral radius in terms of some parameters such as the out-degrees, the maximum out-degree, the second maximum out-degree, the number of vertices, the number of arcs, the average 2-outdegrees of the vertices of D and the parameter α of A α (D). The extremal digraphs attaining these bounds are characterized. It is shown that the bounds obtained improve, in some cases, some of recently given bounds presented in the literature. [ABSTRACT FROM AUTHOR]

Let S n , 2 be the graph obtained by joining each vertex of K 2 to n − 2 isolated vertices, and let S n , 2 − be the graph obtained from S n , 2 by deleting an edge incident to a vertex of degree two. Recently, Zhai, Lin and Shu [20] showed that ρ (G) ≤ 1 + 4 m − 3 2 for any C 5 -free graph of size m ≥ 8 or C 6 -free graph of size m ≥ 22 , with equality if and only if G ≅ S m + 3 2 , 2 (possibly, with some isolated vertices). However, this bound is sharp only for odd m. Motivated by this, we want to obtain a sharp upper bound of ρ (G) for C 5 -free or C 6 -free graphs with m edges. In this paper, we prove that if G is a C 5 -free graph of even size m ≥ 14 or C 6 -free graph of even size m ≥ 74 , and G contains no isolated vertices, then ρ (G) ≤ ρ ˜ (m) , with equality if and only if G ≅ S m + 4 2 , 2 − , where ρ ˜ (m) is the largest root of x 4 − m x 2 − (m − 2) x + (m 2 − 1) = 0. [ABSTRACT FROM AUTHOR]

In 1973 Schwenk [7] proved that almost every tree has a cospectral mate. Inspired by Schwenk's result, in this paper we study the spectrum of two families of trees. The p -sun of order 2 p + 1 is a star K 1 , p with an edge attached to each pendant vertex, which we show to be determined by its spectrum among connected graphs. The (p , q) -double sun of order 2 (p + q + 1) is the union of a p -sun and a q -sun by adding an edge between their central vertices. We determine when the (p , q) -double sun has a cospectral mate and when it is determined by its spectrum among connected graphs. Our method is based on the fact that these trees have few distinct eigenvalues and we are able to take advantage of their nullity to shorten the list of candidates. [ABSTRACT FROM AUTHOR]

A quaternion unit gain graph is a graph where each orientation of an edge is given a quaternion unit, which is the inverse of the quaternion unit assigned to the opposite orientation. In this paper we define the adjacency, Laplacian and incidence matrices for a quaternion unit gain graph and study their properties. These properties generalize several fundamental results from spectral graph theory of ordinary graphs, signed graphs and complex unit gain graphs. Bounds for both the left and right eigenvalues of the adjacency and Laplacian matrix are developed, and the right eigenvalues for the cycle and path graphs are explicitly calculated. [ABSTRACT FROM AUTHOR]

A graph G is F -free, if it contains no F as a subgraph. A Brualdi-Solheid-Turán type problem asks what is the maximum spectral radius of an F -free graph of order n ? Let K a , b • K 3 denote the graph obtained by identifying a vertex of K a , b belonging to the part of size b and a vertex of K 3. In this paper, we consider about a Brualdi-Solheid-Turán type problem on non-bipartite graphs. We prove that if G is a non-bipartite graph with order n ≥ 21 and ρ (G) ≥ ρ (K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3) , then G contains a pentagon unless G ≅ K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3. [ABSTRACT FROM AUTHOR]

First we investigate net-biregular signed graphs with spectrum of the form [ ρ , μ m , λ l ] where λ is non-main; such graphs are necessarily biregular with exactly two main eigenvalues. We provide two constructions of signed graphs with three eigenvalues, where the graphs that arise include net-biregular and net-regular signed graphs having spectrum [ ρ , μ , λ l ] , with λ non-main. Secondly we determine all the connected signed graphs with spectrum [ ρ , μ 2 , λ l ] (l ≥ 2) where λ is non-main: these include a new infinite family of signed graphs which are neither net-regular nor net-biregular. Thus, in contrast to the situation for graphs, a signed graph with two main eigenvalues and one non-main eigenvalue is not necessarily net-biregular. [ABSTRACT FROM AUTHOR]

A blow-up of a graph G , is obtained from G by replacing each vertex v i of G with an independent set V i of n i vertices and joining each vertex in V i with each vertex in V j provided v i v j ∈ E (G). Let M n (G) be the set of all the blow-ups of G such that each n i ≥ 1 and ∑ i = 1 | G | n i = n. Monsalve and Rada (2021) [9] proposed three conjectures on the extremal spectral radii of M n (P k) and M n (C k). In this paper, we confirm the first two conjectures and construct an infinite class of graphs to illustrate the third conjecture is not true. [ABSTRACT FROM AUTHOR]

In 1986, Herbert Wilf asked what kind of graphs have an eigenvector with entries formed only by ±1. In this paper, we answer this question for the adjacency, Laplacian, and signless Laplacian matrices of a graph. To this end, we generalize the concept of an exact graph to the adjacency and signless Laplacian matrices. Infinite families of exact graphs for all those matrices are presented. [ABSTRACT FROM AUTHOR]

In this paper we describe two methods, both inspired from Godsil-McKay switching on simple graphs, to build cospectral gain graphs whose gain group consists of the complex numbers of modulus 1 (the circle group). The results obtained here can be also applied to the Hermitian matrix of mixed graphs. [ABSTRACT FROM AUTHOR]

Let G be an arbitrary group. We define a gain-line graph for a gain graph (Γ , ψ) through the choice of an incidence G -phase matrix inducing ψ. We prove that the switching equivalence class of the gain function on the line graph L (Γ) does not change if one chooses a different G -phase inducing ψ or a different representative of the switching equivalence class of ψ. In this way, we generalize to any group some results proven by N. Reff in the abelian case. The investigation of the orbits of some natural actions of G on the set H Γ of G -phases of Γ allows us to characterize gain functions on Γ, gain functions on L (Γ) , their switching equivalence classes and their balance property. The use of group algebra valued matrices plays a fundamental role and, together with the matrix Fourier transform, allows us to represent a gain graph with Hermitian matrices and to perform spectral computations. Our spectral results also provide some necessary conditions for a gain graph to be a gain-line graph. [ABSTRACT FROM AUTHOR]

A T -gain graph, Φ = (G , φ) , is a graph in which the function φ assigns a unit complex number to each orientation of an edge of G , and its inverse is assigned to the opposite orientation. The associated adjacency matrix A (Φ) is defined canonically. The energy E (Φ) of a T -gain graph Φ is the sum of the absolute values of all eigenvalues of A (Φ). We study the notion of energy of a vertex of a T -gain graph, and establish bounds for it. For any T -gain graph Φ, we prove that 2 τ (G) − 2 c (G) ≤ E (Φ) ≤ 2 τ (G) Δ (G) , where τ (G) , c (G) and Δ (G) are the vertex cover number, the number of odd cycles and the largest vertex degree of G , respectively. Furthermore, using the properties of vertex energy, we characterize the class of T -gain graphs for which E (Φ) = 2 τ (G) − 2 c (G) holds. Also, we characterize the T -gain graphs for which E (Φ) = 2 τ (G) Δ (G) holds. This characterization solves a general version of an open problem. In addition, we establish bounds for the energy in terms of the spectral radius of the associated adjacency matrix. [ABSTRACT FROM AUTHOR]

Let A n be the connected anti-regular graph of order n. It was conjectured that among all threshold graphs on n vertices, A n has the smallest positive eigenvalue and the largest eigenvalue less than −1. Recently, in [1] was given partial results for this conjecture and identified the critical cases where a more refined method is needed. In this paper, we deal with these cases and confirm that conjecture holds. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be the adjacency matrix of G. The graph G is said to have the reciprocal eigenvalue property (R) if A (G) is nonsingular and 1 λ is an eigenvalue of A (G) whenever λ is an eigenvalue of A (G). Further, if λ and 1 λ have the same multiplicity, for each eigenvalue λ , then G is said to have the strong reciprocal eigenvalue property (SR). Till date, all the classes of bipartite graphs that are found to have property (R), are found to have property (SR) and it is not known whether these two properties are equivalent even for the bipartite graphs with a unique perfect matching. Among nonbipartite graphs, there is only one known graph class for which these two properties are not equivalent. In this article, we construct some more classes of nonbipartite graphs with property (R) but not (SR). [ABSTRACT FROM AUTHOR]

A spectral version of extremal graph theory problem is as follows: what is the maximum spectral radius of an H -free graph of order n ? Nikiforov posed a conjecture on spectral extremal value of cycles. In the past decade, much attention has been paid to this conjecture and other questions on spectral extremal graphs. In order to approach to Nikiforov's conjecture, we provide a new conjecture on spectral extremal value involving fans and wheels. Moreover, we show it is true for k = 2. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to highlight the role played by the anti-regular graph within the class of threshold graphs. Using the fact that every threshold graph contains a maximal anti-regular graph, we show that some known results, and new ones, on the spectral properties of threshold graphs can be deduced from (i) the known results on the eigenvalues of anti-regular graphs, (ii) the subgraph structure of threshold graphs, and (iii) eigenvalue interlacing. In particular, we prove a strengthened version of the recently proved fact that no threshold graph contains an eigenvalue in the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] , except possibly the trivial eigenvalues −1 and/or 0, determine the inertia of a threshold graph, and give partial results on a conjecture regarding the optimality of the non-trivial eigenvalues of an anti-regular graph within the class of threshold graphs. [ABSTRACT FROM AUTHOR]

The rank of a digraph is defined as the rank of its adjacency matrix. In this paper we show how to find all digraphs of rank k from the reduced bipartite graphs of rank 2 k. In particular, since the bipartite graphs of rank 2 , 4 and 6 are known, then we characterize digraphs of rank 1 , 2 and 3. The results are based on rank-preserving operations on digraphs such as splitting and fusion of vertices or twin-deletion and vertex-multiplication. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with n vertices v 1 , ... , v n and m edges. Let A (G) = [ a i j ] n × n be the adjacency matrix of G , that is a i j = 1 if v i and v j are adjacent, and a i j = 0 , otherwise. Let λ 1 , ... , λ n be the eigenvalues of A (G). The energy of G , denoted by E (G) , is defined as | λ 1 | + ⋯ + | λ n |. It is well known that 2 m ≤ E (G) ≤ 2 m n. In this paper we improve the latter lower bound and prove that if all eigenvalues of G are non-zero, then E (G) ≥ 2 | λ 1 λ n | | λ 1 | + | λ n | 2 m n , where | λ 1 | ≥ ⋯ ≥ | λ n |. We show that the equality holds if and only if G = n 2 K 2 or G = p K β + 1 ⋃ q T β + 1 , where p and q are some non-negative integers and β ≥ 2 and T β + 1 is the graph K β + 1 , β + 1 ∖ M , where M is a perfect matching of K β + 1 , β + 1. Finally by studying the | λ 1 λ n | | λ 1 | + | λ n | of graphs, we find some lower bounds for the energy of graphs. In particular, we obtain that if G has no eigenvalue in the interval (− 1 , 1) , then E (G) ≥ 2 m 2 n − 2 n , and the equality holds if and only if G is the complete graph K n. [ABSTRACT FROM AUTHOR]

Let G be a graph on n vertices and λ 1 , λ 2 , ... , λ n their eigenvalues. The Estrada index of G is defined as E E (G) = ∑ i = 1 n e λ i . In this paper, we obtain new upper and lower bounds on the Estrada Index of a given graph, considering numerical inequalities present in the literature. [ABSTRACT FROM AUTHOR]

Let G be a graph on n vertices and λ 1 ≥ λ 2 ≥ ... ≥ λ n its eigenvalues. The Estrada index of G is defined as E E (G) = ∑ i = 1 n e λ i . In this work, we use an increasing sequence converging to the λ 1 to obtain an increasing sequence of lower bounds for E E (G). In addition, we generalize this succession for the Estrada index of an arbitrary symmetric nonnegative matrix. [ABSTRACT FROM AUTHOR]

The Gershgorin Circle Theorem is a well-known and efficient method for bounding the eigenvalues of a matrix in terms of its entries. If A is a symmetric matrix, by writing A = B + x 1 , where 1 is the matrix with unit entries, we consider the problem of choosing x to give the optimal Gershgorin bound on the eigenvalues of B , which then leads to one-sided bounds on the eigenvalues of A. We show that this x can be found by an efficient linear program (whose solution can in may cases be written in closed form), and we show that for large classes of matrices, this shifting method beats all existing piecewise linear or quadratic bounds on the eigenvalues. We also apply this shifting paradigm to some nonlinear estimators and show that under certain symmetries this also gives rise to a tractable linear program. As an application, we give a novel bound on the lowest eigenvalue of a adjacency matrix in terms of the "top two" or "bottom two" degrees of the corresponding graph, and study the efficacy of this method in obtaining sharp eigenvalue estimates for certain classes of matrices. [ABSTRACT FROM AUTHOR]

Abstract In this study we derive certain upper bounds for the largest eigenvalue (called the index and denoted λ 1) of a signed graph. In particular, we prove the following upper bound: λ 1 2 ≤ max ⁡ { d i m i − n i : 1 ≤ i ≤ n } , where d i is the vertex degree of i , m i = 1 d i ∑ j ∼ i d j and n i = ∑ j ∼ i (| N i σ (i j) ∩ N j | − | | N i σ (i j) ∩ N j σ (i j) | − | N i σ (i j) ∩ N j − σ (i j) | |) , with N i , N i + and N i − denoting the neighbourhood, the positive neighbourhood and the negative neighbourhood of a vertex i. In our proofs we use standard techniques transferred from the field of (unsigned, simple) graphs. Using the fact that all switching equivalent signed graphs share the same spectrum, we derive some more sophisticated bounds. [ABSTRACT FROM AUTHOR]

Abstract The spectral radius of a graph is the largest eigenvalue of the adjacency matrix corresponding to this graph. Let G be a graph with long pendant paths. In this note, we estimate the spectral radius of G , by obtaining appropriate upper and lower bounds. As an application, the spectral radius of some k-ary trees are estimated. [ABSTRACT FROM AUTHOR]

Abstract A (1 , ≤ ℓ) -identifying code in digraph D is a dominating subset C of vertices of D , such that all distinct subsets of vertices of D with cardinality at most ℓ have distinct closed in-neighborhoods within C. As far as we know, it is the very first time that the spectral graph theory has been applied to the identifying codes. We give a new method to obtain an upper bound on ℓ for digraphs. The results obtained here can also be applied to graphs. [ABSTRACT FROM AUTHOR]

Abstract Finding a diagonal matrix congruent to A − c I for constants c , where A is the adjacency matrix of a graph G allows us to quickly tell the number of eigenvalues in a given interval. If G has clique-width k and a corresponding k -expression is known, then diagonalization can be done in time O (poly (k) n) where n is the order of G. [ABSTRACT FROM AUTHOR]

Abstract Let μ be an eigenvalue of a simple graph G with multiplicity k ≥ 1. A star complement for μ in G is an induced subgraph of G of order n − k with no eigenvalue μ. In this paper, we study the maximal graphs with the star S m as a star complement for −2. The maximal graphs with S 3 , S 4 , S 13 and S 21 as a star complement for −2 are described. We also describe the regular graphs with K 2 , s (s ≥ 2) as a star complement for an eigenvalue μ. [ABSTRACT FROM AUTHOR]

In this paper we develop the concept of energy of a vertex introduced in Arizmendi and Juarez-Romero (2018). We derive basic inequalities, continuity properties, give examples and extend the definition to locally finite graphs. [ABSTRACT FROM AUTHOR]

We study the eigenvalues of the unique connected anti-regular graph A n . Using Chebyshev polynomials of the second kind, we obtain a trigonometric equation whose roots are the eigenvalues and perform elementary analysis to obtain an almost complete characterization of the eigenvalues. In particular, we show that the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] contains only the trivial eigenvalues λ = − 1 or λ = 0 , and any closed interval strictly larger than Ω will contain eigenvalues of A n for all n sufficiently large. We also obtain bounds for the maximum and minimum eigenvalues, and for all other eigenvalues we obtain interval bounds that improve as n increases. Moreover, our approach reveals a more complete picture of the bipartite character of the eigenvalues of A n , namely, as n increases the eigenvalues are (approximately) symmetric about the number − 1 2 . We also obtain an asymptotic distribution of the eigenvalues as n → ∞ . Finally, the relationship between the eigenvalues of A n and the eigenvalues of a general threshold graph is discussed. [ABSTRACT FROM AUTHOR]

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected graph. Let 0 ≤ α ≤ 1 . Let A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) where D ( G ) and A ( G ) are the diagonal matrix of the vertex degrees of G and the adjacency matrix of G , respectively. Let p ( G ) > 0 and q ( G ) be the number of pendant vertices and quasi-pendant vertices of G , respectively. Let m G ( α ) be the multiplicity of α as an eigenvalue of A α ( G ) . It is proved that m G ( α ) ≥ p ( G ) − q ( G ) with equality if each internal vertex is a quasi-pendant vertex. If there is at least one internal vertex which is not a quasi-pendant vertex, the equality m G ( α ) = p ( G ) − q ( G ) + m N ( α ) is determined in which m N ( α ) is the multiplicity of α as an eigenvalue of the matrix N . This matrix is obtained from A α ( G ) taking the entries corresponding to the internal vertices which are non quasi-pendant vertices. These results are applied to search for the multiplicity of α as an eigenvalue of A α ( G ) when G is a path, a caterpillar, a circular caterpillar, a generalized Bethe tree or a Bethe tree. For the Bethe tree case, a simple formula for the nullity is given. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . This paper presents some extremal results about the spectral radius ρ α ( G ) of A α ( G ) that generalize previous results about ρ 0 ( G ) and ρ 1 / 2 ( G ) . In particular, write B p , q , r be the graph obtained from a complete graph K p by deleting an edge and attaching paths P q and P r to its ends. It is shown that if α ∈ [ 0 , 1 ) and G is a graph of order n and diameter at least k , then ρ α ( G ) ≤ ρ α ( B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ ) , with equality holding if and only if G = B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ . This result generalizes results of Hansen and Stevanović [5] , and Liu and Lu [7] . [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For any real α ∈ [ 0 , 1 ] , Nikiforov [3] defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . The largest eigenvalue of A α ( G ) is called the A α -spectral radius of G . In this paper, we give three edge graft transformations on A α -spectral radius. As applications, we determine the unique graph with maximum A α -spectral radius among all connected graphs with diameter d , and determine the unique graph with minimum A α -spectral radius among all connected graphs with given clique number. In addition, some bounds on the A α -spectral radius are obtained. [ABSTRACT FROM AUTHOR]

We give counterexamples to a result in F. Esser and F. Harary [2, Theorem 3] asserting that two nonisomorphic complete r -partite graphs with the same number of vertices have different spectral radii. We then derive some results on invariant factors and apply them to obtain relationship between the parameters of integral complete multipartite graphs and their integer eigenvalues. Necessary conditions for complete multipartite graphs to be integral are obtained. [ABSTRACT FROM AUTHOR]