Search

Given a pair of real symmetric matrices A , B ∈ R n × n with nonzero patterns determined by the edges of any pair of chosen graphs on n vertices, we consider an inverse eigenvalue problem for the structured matrix C = [ A B I O ] ∈ R 2 n × 2 n. We conjecture that C can attain any spectrum that is closed under conjugation. We use a structured Jacobian method to prove this conjecture for A and B of orders at most 4 or when the graph of A has a Hamilton path, and prove a weaker version of this conjecture for any pair of graphs with a restriction on the multiplicities of eigenvalues of C. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be the adjacency matrix of G. A diagonal matrix with diagonal entries ±1 is called a signature matrix. If A (G) is nonsingular and X = S A (G) − 1 S − 1 is entrywise nonnegative for some signature matrix S , then X can be viewed as the adjacency matrix of a unique weighted graph. It is called the inverse of G , denoted by G +. A graph G is said to have the reciprocal eigenvalue property (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 (property (SR)). It is known that for a tree T , the following conditions are equivalent: a) T + is isomorphic to T , b) T has property (R), c) T has property (SR) and d) T is a corona tree (it is a tree which is obtained from another tree by adding a new pendant at each vertex). Studies on the inverses, property (R) and property (SR) of bipartite graphs are available in the literature. However, their studies for the non-bipartite graphs are rarely done. In this article, we study the inverse and property (SR) for non-bipartite graphs. We first introduce an operation, which helps us to study the inverses of non-bipartite graphs. As a consequence, we supply a class of non-bipartite graphs for which the inverse graph G + exists and G + is isomorphic to G. It follows that each graph G in this class has property (SR). [ABSTRACT FROM AUTHOR]

We provide three infinite families of graphs in the Johnson and Grassmann schemes that are not uniquely determined by their spectrum. We do so by constructing graphs that are cospectral but non-isomorphic to these graphs. [ABSTRACT FROM AUTHOR]

In this paper, we take a modest first step towards a systematic study of chromatic numbers of Cayley graphs on abelian groups. We lose little when we consider these graphs only when they are connected and of finite degree. As in the work of Heuberger and others, in such cases the graph can be represented by an m × r integer matrix, where we call m the dimension and r the rank. Adding or subtracting rows produces a graph homomorphism to a graph with a matrix of smaller dimension, thereby giving an upper bound on the chromatic number of the original graph. In this article we develop the foundations of this method. As a demonstration of its utility, we provide an alternate proof of Payan's theorem, which states that a cubelike graph (i.e., a Cayley graph on the product Z 2 × ⋯ × Z 2 of the integers modulo 2 with itself finitely many times) cannot have chromatic number 3. In a series of follow-up articles using the method of Heuberger matrices, we completely determine the chromatic number in cases with small dimension and rank, as well as prove a generalization of Zhu's theorem on the chromatic number of 6-valent integer distance graphs. [ABSTRACT FROM AUTHOR]

A graph is a cograph if and only if it has no induced path on 4 vertices. The twin reduction graph of a graph G is denoted by R G. In this article, we describe the Laplacian eigenvalues and eigenvectors of a cograph G using its twin reduction graph R G , and characterize cographs with even and odd integer eigenvalues, respectively. We provide a construction for the Laplacian cospectral cographs. Further, we provide a complete description of the Laplacian spectrum of H -join of graphs when H is a cograph, and then obtain bounds for the algebraic connectivity of such graphs. We also provide some interesting observations on Hadamard diagonalizable cographs. [ABSTRACT FROM AUTHOR]

For q ∈ R , the Q - matrix Q = Q q of a connected simple graph G = (V , E) is Q q = (q ∂ (x , y)) x , y ∈ V , where ∂ denotes the path-length distance. Describing the set π (G) consisting of those q ∈ R for which Q q is positive semidefinite is fundamental in asymptotic spectral analysis of graphs from the viewpoint of quantum probability theory. Assume that G has at least two vertices. Then π (G) is easily seen to be a nonempty closed subset of the interval [ − 1 , 1 ]. In this note, we show that π (G) = [ − 1 , 1 ] if and only if G is isometrically embeddable into a hypercube (infinite-dimensional if G is infinite) if and only if G is bipartite and does not possess certain five-vertex configurations, an example of which is an induced K 2 , 3. [ABSTRACT FROM AUTHOR]

An odd [ 1 , b ] -factor of a graph G is a spanning subgraph F of G with d F (x) ∈ { 1 , 3 , ⋯ , b } for every x ∈ V (G) , where b is a positive odd integer. Let | E (G) | be the size of G , and let ρ (G) be the spectral radius of G. In this article, we first verify three lower bounds for | E (G) | in a graph G of even order n to guarantee the existence of an odd [ 1 , b ] -factor in G. Then we prove two lower bounds for ρ (G) in a graph G of even order n to guarantee the existence of an odd [ 1 , b ] -factor in G. Furthermore, we create some extremal graphs to show all the lower bounds derived in this article are sharp. [ABSTRACT FROM AUTHOR]

We develop a general spectral framework to analyze quantum fractional revival in quantum spin networks. In particular, we determine when the adjacency algebra of a graph contains a matrix of a block diagonal form required for fractional revival, and introduce generalizations of the notions of cospectral and strongly cospectral vertices to arbitrary subsets of vertices. We give several constructions of graphs admitting fractional revival. This work resolves two open questions of Chan et al. (2019) [6]. [ABSTRACT FROM AUTHOR]

For a simple graph G , let n (G) , η (G) , r (G) and g (G) be respectively the order, the nullity, the rank and the girth of G. It was shown by Cheng and Liu (2007) that for every graph G , η (G) ≤ { n (G) − g (G) + 2 if 4 | g (G) n (G) − g (G) if 4 ∤ g (G) . Connected graphs G with η (G) = n (G) − g (G) + 2 and n (G) − g (G) respectively have been characterized by Zhou et al. (2021). In this paper, we characterize connected graphs G with η (G) = n (G) − g (G) − 1. [ABSTRACT FROM AUTHOR]

In this work, the inverse eigenvalue problem is completely solved for a subfamily of clique-path graphs, in particular for lollipop graphs and generalized barbell graphs. For a matrix A with associated graph G , a new technique utilizing the strong spectral property is introduced, allowing us to construct a matrix A ′ whose graph is obtained from G by appending a clique while arbitrary list of eigenvalues is added to the spectrum. Consequently, many spectra are shown realizable for block graphs. [ABSTRACT FROM AUTHOR]

We introduce a pictorial notation for certain tensors arising in the study of association schemes, based on earlier ideas of Terwilliger, Neumaier and Jaeger. These tensors, which we call "scaffolds", obey a simple set of rules which generalize common linear-algebraic operations such as trace, matrix product and entrywise product. We first study an elementary set of "moves" on scaffolds and illustrate their use in combinatorics. Next we re-visit results of Dickie, Suzuki and Terwilliger. The main new results deal with the relationships among vector spaces of scaffolds with edge weights chosen from a fixed coherent algebra and various underlying diagrams. As one consequence, we provide simple descriptions of the Terwilliger algebras of triply regular and dually triply regular association schemes. We finish with a conjecture connecting the duality of Bose-Mesner algebras to the graph-theoretic duality of circular planar graphs. [ABSTRACT FROM AUTHOR]

Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations. [ABSTRACT FROM AUTHOR]

The change in geometric multiplicity, associated with perturbing a particular pair of off-diagonal entries, in a combinatorially symmetric matrix is investigated. First, we focus upon a Hermitian matrix, with a general graph, when the perturbation is Hermitian. This generalizes prior work in case the graph is a tree; the possibilities are much richer. Then, we turn to general matrices over a field. In both cases, by classifying the incident vertices, all possibilities for the change in geometric multiplicity are identified. Then, examples are given to show that each possibility may actually occur. In some instance, the change in geometric multiplicity depends upon the numerical value of the perturbation, and it matters that both off-diagonal entries change. However, in most instances, the change is qualitatively determined. [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]

We show that the column sum optimization problem , of finding a (0 , 1) -matrix with prescribed row sums which minimizes the sum of evaluations of given functions at its column sums, can be solved in polynomial time, either when all functions are the same or when all row sums are bounded by any constant. We conjecture that the more general line sum optimization problem , of finding a matrix minimizing the sum of given functions evaluated at its row sums and column sums, can also be solved in polynomial time. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n with normalized Laplacian eigenvalues ρ 1 ≥ ρ 2 ≥ ⋯ ≥ ρ n − 1 ≥ ρ n = 0. Let m G (ρ i) (1 ≤ i ≤ n) be the multiplicity of the normalized Laplacian eigenvalue ρ i of G. In this paper, we give some necessary and sufficient conditions for a connected graph G to have m G (ρ i) = n − 3 for some i. We also discuss about graphs with m G (ρ n − 2) = n − k. Moreover, we completely characterize the connected graphs with m G (ρ n − 1) = n − k for sufficiently large n. [ABSTRACT FROM AUTHOR]

The k -independence number of a graph is the maximum size of a set of vertices at pairwise distance greater than k. A graph is called k -partially walk-regular if the number of closed walks of a given length l ≤ k , rooted at a vertex v , only depends on l. In particular, a distance-regular graph is also k -partially walk-regular for any k. In this paper, we introduce a new family of polynomials obtained from the spectrum of a graph, called minor polynomials. These polynomials, together with the interlacing technique, allow us to give tight spectral bounds on the k -independence number of a k -partially walk-regular graph. With some examples and infinite families of graphs whose bounds are tight, we also show that the odd graph O ℓ with ℓ odd has no 1-perfect code. Moreover, we show that our bound coincides, in general, with the Delsarte's linear programming bound and the Lovász theta number θ , the best ones to our knowledge. In fact, as a byproduct, it is shown that the given bounds also apply for θ and Θ, the Shannon capacity of a graph. Moreover, apart from the possible interest that the minor polynomials can have, our approach has the advantage of yielding closed formulas and, so, allowing asymptotic analysis. [ABSTRACT FROM AUTHOR]

A graphical design is a proper subset of vertices of a graph on which many eigenfunctions of the Laplacian operator have mean value zero. In this paper, we show that extremal independent sets make extremal graphical designs, that is, a design on which the maximum possible number of eigenfunctions have mean value zero. We then provide examples of such graphs and sets, which arise naturally in extremal combinatorics. We also show that sets which realize the isoperimetric constant of a graph make extremal graphical designs, and provide examples for them as well. We investigate the behavior of graphical designs under the operation of weak graph product. In addition, we present a family of extremal graphical designs for the hypercube graph. [ABSTRACT FROM AUTHOR]

We introduce the set G SSP of all simple graphs G with the property that each symmetric matrix corresponding to a graph G ∈ G SSP has the strong spectral property. We find several families of graphs in G SSP and, in particular, characterise the trees in G SSP. [ABSTRACT FROM AUTHOR]

Let π = { V 1 , ... , V r } be an equitable partition of the vertex set of a directed graph (digraph) X. It is well known that the characteristic polynomial ϕ (X / π , x) of a quotient graph X / π divides that of X , but the remainder part is not well investigated. In this paper, we define a deletion graph X \ π over an equitable partition π , which is a signed directed graph defined for a fixed set of deleting vertices { v ‾ i ∈ V i , i = 1 , ⋯ , r } , and give a similarity transformation exchanging the adjacency matrix A (X) which is compatible with the equitable partition for a block triangular matrix whose diagonal blocks are the adjacency matrix of the quotient graph and the deletion graph. In fact, we show the result for more general matrices including adjacency matrix of graphs, and as corollaries, we show the followings: (i) a decomposition formula of the reciprocal of the Ihara-Bartholdi zeta function over an equitably partitioned undirected graph into the quotient graph part and the deletion graph part, and (ii) Chen and Chen's result ([4, Theorem 3.1]) on the Ihara-Bartholdi zeta functions on generalized join graphs, and (iii) Teranishi's result [32, Theorem 3.3]. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n and also let ρ (G) be the spectral radius of the graph G. In this paper, we prove that ρ (G) ≤ ρ 2 (G − v k) + 2 d k − 1 for any non-isolated vertex v k of degree d k in G , thus confirming a conjecture posed by Guo et al. (2019) [3]. Moreover, we characterized all connected graphs for which this bound is attained. [ABSTRACT FROM AUTHOR]

The structure of an undirected graph is completely determined by a symmetric matrix: its adjacency matrix with respect to an ordering of its vertices; and that matrix can be used to define an integral quadratic form. The main purpose of this paper is to raise this question: "What can quadratic forms tell us about graphs?" As an initial answer, the theory of quadratic forms will be applied to the graph isomorphism problem. The essential definitions and facts from the theory of quadratic forms will be sketched without proof. [ABSTRACT FROM AUTHOR]

This work introduces a general concept of center for graphs, built on the model of the characteristic set ([12,14]) of trees. We define it as the set of cycles in a specific directed graph associated with the original graph G , and we let it depend on a function μ. In the case of trees we consider particular instances of μ given as weights of rooted subtrees, thus retrieving the characteristic set and, interestingly, the eccentricity-center. We investigate when the center of a graph G is simple – i.e., consisting of a unique cycle – and quasi-simple – i.e., inducing a connected subgraph of G. In particular, we prove that the center of a caterpillar tree associated with the so-called combinatorial Perron parameter ρ c (studied in [2] and [3]) is always simple. We also make use of a discrete version of concavity to generate examples of simple and quasi-simple centers for graphs. [ABSTRACT FROM AUTHOR]

We introduce the concept of distance ideals of graphs, which can be regarded as a generalization of the Smith normal form and the spectra of the distance matrix and the Laplacian distance matrix of a graph. We also obtain a classification of the graphs with at most one trivial distance ideal. [ABSTRACT FROM AUTHOR]

The nullity η (G) of G is the multiplicity of 0 as an eigenvalue of A (G). In this paper, we completely solve the following conjecture proposed by Zhou, Wong and Sun in [Linear Algebra and its Applications, 555 (2018) 314-320]: Let G be a connected graph of order n with nullity η (G) and the maximum degree Δ ≥ 2. Then η (G) ≤ (Δ − 2) n + 2 Δ − 1 , the equality holds if and only if G ≅ C n (n ≡ 0 (m o d 4)) or G ≅ K Δ , Δ. [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 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]

Let M be a partitioned matrix and B be its equitable quotient matrix. In this paper, we prove the inclusion of their spectra σ (B) ⊆ σ (M) , and the equality of their spectral radii ρ (B) = ρ (M) if M is nonnegative. Moreover, σ (M) is shown to be completely determined by σ (B) if M is from a class of special matrices. Then we apply these results to obtain the spectra of some well-known matrices associated with graphs or digraphs, and then determine the extremal values of different spectral radii associated with connected graphs or strongly connected digraphs with given vertex connectivity. [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 Let G be a graph of order n. Also let λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n be the eigenvalues of graph G. In this paper, we present the following upper bound on the sum of the k (≤ n) largest eigenvalues of G in terms of the order n and negative inertia θ (the number of negative eigenvalues): ∑ i = 1 k λ i ≤ n 2 (θ + 1) (θ + θ (k θ + k − 1) ) with equality holding if and only if G ≅ n K 1 or G ≅ p K ‾ t (n = p t , p ≥ 2) with k = 1 (where p K ‾ t is the complete p -partite graph of p t vertices with all partition sets having size t). Moreover, we obtain a sharp upper bound on the energy of bipartite graphs with given order n and rank r. We also propose an open problem as follows: Characterize all connected d -regular bipartite graphs of order n with 5 distinct eigenvalues and rank r = 2 n 2 (4 d − n) 2 , where d > n 4. Finally we give a partial solution to this problem. [ABSTRACT FROM AUTHOR]

Abstract We investigate the change in the multiplicities of the eigenvalues of a Hermitian matrix with a simple graph G , when edges are inserted into G or removed from G. We focus upon cases in which the multiplicity of the eigenvalue does not change due to inserting or removing edges incident to a vertex. Furthermore, we show how the change in the multiplicities of the eigenvalues occur, when two disjoint graphs are connected with one edge, based upon the status of the vertices that are connected. Lastly, we give the possible classifications of cut-edges in a graph and characterize the occurrence of each possible status. [ABSTRACT FROM AUTHOR]

Abstract A spanning tree of a graph is a connected subgraph on all vertices with the minimum number of edges. The number of spanning trees in a graph G is given by Matrix Tree Theorem in terms of principal minors of Laplacian matrix of G. We show a similar combinatorial interpretation for principal minors of signless Laplacian Q. We also prove that the number of odd cycles in G is less than or equal to det ⁡ (Q) 4 , where the equality holds if and only if G is a bipartite graph or an odd-unicyclic graph. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n and size m with Laplacian eigenvalues μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n = 0 . The Kirchhoff index of G , denoted by Kf , is defined as: K f = n ∑ i = 1 n − 1 1 μ i . The Laplacian-energy-like invariant ( L E L ) and the Laplacian energy ( L E ) of the graph G , are defined as: L E L = ∑ i = 1 n − 1 μ i and L E = ∑ i = 1 n | μ i − 2 m n | , respectively. We obtain two relations on LEL with Kf , and LE with Kf . For two classes of graphs, we prove that L E L > K f . Finally, we present an upper bound on the ratio L E / L E L and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph of order n with m edges. Denote by D ( G ) the diagonal matrix of its vertex degrees and by A ( G ) its adjacency matrix. Then the Laplacian matrix of graph G is L ( G ) = D ( G ) − A ( G ) . Among all eigenvalues of the Laplacian matrix L ( G ) of graph G , the most studied is the second smallest, called the algebraic connectivity a ( G ) of a graph. Let d ‾ ( G ) and δ ( G ) be the average degree and the minimum degree of graph G , respectively. In this paper we characterize all graphs for which ( i ) a ( G ) = 1 with δ ( G ) ≥ ⌈ n − 1 2 ⌉ , and ( i i ) a ( G ) = 2 with δ ( G ) ≥ n 2 . In [1] , Aouchiche mentioned a conjecture involving the algebraic connectivity a ( G ) and the average degree d ‾ ( G ) of graph G : a ( G ) − d ‾ ( G ) ≥ 4 − n − 4 n with equality holding if and only if G ‾ ≅ K 1 , n − 2 ∪ K 1 ( K 1 , n − 2 is a star of order n − 1 and G ‾ is the complement of graph G ). Here we prove this conjecture. [ABSTRACT FROM AUTHOR]

By the well-known Perron–Frobenius Theorem [3] , for a connected graph G , its largest eigenvalue strictly increases when an edge is added. We are interested in how the other eigenvalues of a connected graph change when edges are added. Examples show that all cases are possible: increased, decreased, unchanged. In this paper, we consider the effect on the eigenvalues by suitably adding edges in particular families, say the family of connected graphs with clusters. By using the result, we also consider the effect on the energy by suitably adding edges to the graphs of the above families. [ABSTRACT FROM AUTHOR]

Let n ≥ k ≥ 2 be two integers and S a subset of { 0 , 1 , … , k − 1 } . The graph J S ( n , k ) has as vertices the k -subsets of the n -set [ n ] = { 1 , … , n } and two k -subsets A and B are adjacent if | A ∩ B | ∈ S . In this paper, we use Godsil–McKay switching to prove that for m ≥ 0 , k ≥ max ⁡ ( m + 2 , 3 ) and S = { 0 , 1 , . . . , m } , the graphs J S ( 3 k − 2 m − 1 , k ) are not determined by spectrum and for m ≥ 2 , n ≥ 4 m + 2 and S = { 0 , 1 , . . . , m } the graphs J S ( n , 2 m + 1 ) are not determined by spectrum. We also report some computational searches for Godsil–McKay switching sets in the union of classes in the Johnson scheme for k ≤ 5 . [ABSTRACT FROM AUTHOR]

In this paper, we give some bounds on the signless Laplacian index of graphs in terms of independence number. In addition, these results disprove a conjecture in [3] involving the signless Laplacian index and independence number of graphs. [ABSTRACT FROM AUTHOR]

Recently, it has been noticed that if the graph of an n-by-n complex matrix is a tree, then normality of the matrix is equivalent to three conditions, associated with the edges of the graph, that are much simpler than checking the standard definition of normality. Here, we characterize the precise class of graphs (much more general than trees), for which the three conditions are equivalent to normality, under a slight (and necessary) regularity condition. The graphs are those that are both triangle and 4-cycle free. For triangle-free graphs, normality implies absolute symmetry, under the same regularity condition. The results permit strong applications to real matrices, and to the notions of “principal normality”, and “essentially Hermitian”. [ABSTRACT FROM AUTHOR]

Terpai [21] proved the Nordhaus–Gaddum bound that μ ( G ) + μ ( G ‾ ) ≤ 4 n / 3 − 1 , where μ ( G ) is the spectral radius of a graph G with n vertices. Let s + denote the sum of the squares of the positive eigenvalues of G . We prove that s + ( G ) + s + ( G ‾ ) < 2 n and conjecture that s + ( G ) + s + ( G ‾ ) ≤ 4 n / 3 − 1 . We have used AutoGraphiX and Wolfram Mathematica to search for a counter-example. We also consider Nordhaus–Gaddum bounds for s + and bounds for the Randić index. [ABSTRACT FROM AUTHOR]

For given distinct numbers λ 1 ± μ 1 i , λ 2 ± μ 2 i , … , λ k ± μ k i ∈ C ∖ R and γ 1 , γ 2 , … , γ l ∈ R , and a given graph G with a matching of size at least k , we will show that there is a real matrix whose eigenvalues are the given numbers and its graph is G . In particular, this implies that any real matrix with distinct eigenvalues is similar to a real, irreducible, tridiagonal matrix. [ABSTRACT FROM AUTHOR]

We conjecture that all connected graphs of order n have von Neumann entropy at least as great as the star K 1 , n − 1 and prove this for almost all graphs of order n . We show that connected graphs of order n have Rényi 2-entropy at least as great as K 1 , n − 1 and for α > 1 , K n maximizes Rényi α -entropy over graphs of order n . We show that adding an edge to a graph can lower its von Neumann entropy. [ABSTRACT FROM AUTHOR]

A bag B a g p , q is a graph obtained from a complete graph K p by replacing an edge uv by a path P q . In this paper, we show that for all the connected graphs of order n ≥ 5 with signless Laplacian index q 1 ( G ) and radius r a d ( G ) , q 1 ( G ) ⋅ r a d ( G ) is maximum for and only for the graph B a g n − 2 s + 3 , 2 s − 1 , where s = ⌈ n / 4 ⌉ . This solves a conjecture in [6] on the signless Laplacian index involving the radius. [ABSTRACT FROM AUTHOR]

The energy of a graph is defined as the sum of the absolute values of all eigenvalues of the graph. The subgraph grafting operation on a graph is a kind of subgraph moving between two vertices of the graph. In this paper, we introduce two new subgraph grafting operations on bipartite graph and show how the graph energy changes under these subgraph grafting operations. As the application of these operations, we determine the trees with the third and fourth minimal energies in the set of trees with given order and domination number. [ABSTRACT FROM AUTHOR]

In this paper we introduce a parameter Mm ( G ) , defined as the maximum over the minimal multiplicities of eigenvalues among all symmetric matrices corresponding to a graph G . We develop basic properties of Mm ( G ) and compute it for several families of graphs. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n with m edges and clique number ω . Let μ 1 ≥ μ 2 ≥ … ≥ μ n = 0 be the Laplacian eigenvalues of G and let σ = σ ( G ) ( 1 ≤ σ ≤ n ) be the largest positive integer such that μ σ ≥ 2 m n . In this paper we study the relation between σ and ω . In particular, we provide the answer to Problem 2.3 raised in Pirzada and Ganie (2015) [15] . Moreover, we characterize all connected threshold graphs with σ < ω − 1 , σ = ω − 1 and σ > ω − 1 . We obtain Nordhaus–Gaddum-type results for σ . Some relations between σ with other graph invariants are obtained. [ABSTRACT FROM AUTHOR]

We correct an error in the statements of (2) of Lemma 2.2, (2) of Corollary 2.1 and (2) of Theorem 2.1 of [Linear Algebra Appl. 548 (2018) 57–65]. [ABSTRACT FROM AUTHOR]

If T is a labelled tree, a matrix A is totally positive relative to T , principal submatrices of A associated with deletion of pendent vertices of T are P-matrices, and A has positive determinant, then the smallest absolute eigenvalue of A is positive with multiplicity 1 and its eigenvector is signed according to T . This conclusion has been incorrectly conjectured under weaker hypotheses. [ABSTRACT FROM AUTHOR]

The distance matrix of a graph G is the matrix containing the pairwise distances between vertices. The distance eigenvalues of G are the eigenvalues of its distance matrix and they form the distance spectrum of G . We determine the distance spectra of double odd graphs and Doob graphs, completing the determination of distance spectra of distance regular graphs having exactly one positive distance eigenvalue. We characterize strongly regular graphs having more positive than negative distance eigenvalues. We give examples of graphs with few distinct distance eigenvalues but lacking regularity properties. We also determine the determinant and inertia of the distance matrices of lollipop and barbell graphs. [ABSTRACT FROM AUTHOR]

A spectral characterization of the matching number (the size of a maximum matching) of a graph is given. More precisely, it is shown that the graphs G of order n whose matching number is k are precisely those graphs with the maximum skew rank 2 k such that for any given set of k distinct nonzero purely imaginary numbers there is a real skew-symmetric matrix A with graph G whose spectrum consists of the given k numbers, their conjugate pairs and n − 2 k zeros. [ABSTRACT FROM AUTHOR]

The energy of a simple graph G , E ( G ) , is the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of line graph and the signless Laplacian energy of graph G are denoted by E ( L G ) ( L G is the line graph of G ) and LE + ( G ) , respectively. In this paper we obtain a relation between E ( L G ) and LE + ( G ) of graph G . From this relation we characterize all the graphs satisfying E ( L G ) = LE + ( G ) + 4 m n − 4 . We also present a relation between E ( G ) and E ( L G ) . Moreover, we give an upper bound on E ( L G ) of graph G and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]