Search

A spanning k -tree of a connected graph G is a spanning tree in which each vertex admits degree at most k. It is easy to see that a spanning 2-tree is a Hamiltonian path. Hence, a spanning k -tree is an extended concept of a Hamiltonian path. Let Q (G) denote the distance signless Laplacian matrix of a graph G. The largest eigenvalue η 1 (G) of Q (G) is called the distance signless Laplacian spectral radius of G. Liu and Li characterized a connected graph with a perfect matching with respect to the distance signless Laplacian spectral radius (Liu and Li, 2021). Win characterized a connected graph with a spanning k -tree via the number of connected components (Win, 1989). Motivated by Liu and Li's and Win's results, in this paper we investigate the relations between the spanning k -tree and the distance signless Laplacian spectral radius in a connected graph and prove an upper bound for η 1 (G) in a connected graph G to guarantee the existence of a spanning k -tree. [ABSTRACT FROM AUTHOR]

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]

Let G be a connected graph of order n, where n is a positive integer. A spanning subgraph F of G is called a path-factor if every component of F is a path of order at least 2. A P ≥ k -factor means a path-factor in which every component admits order at least k ( k ≥ 2 ). The distance matrix D (G) of G is an n × n real symmetric matrix whose (i, j)-entry is the distance between the vertices v i and v j . The distance signless Laplacian matrix Q (G) of G is defined by Q (G) = T r (G) + D (G) , where Tr(G) is the diagonal matrix of the vertex transmissions in G. The largest eigenvalue η 1 (G) of Q (G) is called the distance signless Laplacian spectral radius of G. In this paper, we aim to present a distance signless Laplacian spectral radius condition to guarantee the existence of a P ≥ 2 -factor in a graph and claim that the following statements are true: (i) G admits a P ≥ 2 -factor for n ≥ 4 and n ≠ 7 if η 1 (G) < θ (n) , where θ (n) is the largest root of the equation x 3 - (5 n - 3) x 2 + (8 n 2 - 23 n + 48) x - 4 n 3 + 22 n 2 - 74 n + 80 = 0 ; (ii) G admits a P ≥ 2 -factor for n = 7 if η 1 (G) < 25 + 161 2 . [ABSTRACT FROM AUTHOR]

In this paper, we discuss spectrum and energy of Arithmetic function signed graphs with respect to an arithmetical function and present some results. [ABSTRACT FROM AUTHOR]

Schur decompositions and the corresponding Schur forms of a single matrix, a pair of matrices, or a collection of matrices associated with the periodic eigenvalue problem are frequently used and studied. These forms are upper-triangular complex matrices or quasi-upper-triangular real matrices that are equivalent to the original matrices via unitary or, respectively, orthogonal transformations. In general, for theoretical and numerical purposes we often need to reduce, by admissible transformations, a collection of matrices to the Schur form. Unfortunately, such a reduction is not always possible. In this paper we describe all collections of complex (real) matrices that can be reduced to the Schur form by the corresponding unitary (orthogonal) transformations and explain how such a reduction can be done. We prove that this class consists of the collections of matrices associated with pseudoforest graphs. In other words, we describe when the Schur form of a collection of matrices exists and how to find it. [ABSTRACT FROM AUTHOR]

In this paper we firstly prove that the CDp curvature condition always satisfies for p ≥ 2 on any connected locally finite graph. We show this property does not hold for 1 < p < 2. We also derive a lower bound for the first nonzero eigenvalue of the p-Laplace operator on a connected finite graph with the CDp(m, K) condition for the case that 1 < p ≤ 2 , m > 2 (p − 1) 2 p and K > 0. [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]

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]

Let G be a connected graph of even order n. An odd [1, b]-factor of G is a spanning subgraph F of G such that dF(v) ∈ {1, 3, 5, ⋯, b} for any v ∈ V(G), where b is positive odd integer. The distance matrix Ɗ(G) of G is a symmetric real matrix with (i, j)-entry being the distance between the vertices vi and vj. The distance signless Laplacian matrix Q(G) of G is defined by Q(G), where Tr(G) is the diagonal matrix of the vertex transmissions in G. The largest eigenvalue η1(G) of Q(G) is called the distance signless Laplacian spectral radius of G. In this paper, we verify sharp upper bounds on the distance signless Laplacian spectral radius to guarantee the existence of an odd [1, b]-factor in a graph; we provide some graphs to show that the bounds are optimal. [ABSTRACT FROM AUTHOR]

The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U = c 1 A + c 2 D + c 3 I + c 4 J , with c i ∈ R and c 1 ≠ 0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues. [ABSTRACT FROM AUTHOR]

We consider the spectral Neumann problem for the Laplace operator on a thin lattice comprised of nodes and ligaments. We pose the classical Pauling model on a one-dimensional graph which describes the multidimensional problem in the first approximation contains ordinary differential equations on its edges with Kirchhoff transmission conditions at its vertices. We construct two-term asymptotics for the spectral pairs {eigenvalue, eigenfunction} of the problem on the lattice. Basing on this analysis, we propound some refined asymptotic model on the graph with shortened edges that includes certain integral characteristics of the junction zones and actually accounts in the first approximation not only for the edge lengths but also for their arrangement, as well as for the shape and size of the nodes. [ABSTRACT FROM AUTHOR]

Gain graphs are graphs where the edges are given some orientation and labeled with the elements (called gains) from a group so that the gains are inverted when we reverse the direction of the edges. Generalizing the notion of gain graphs, skew gain graphs have the property that the gain of a reversed edge is the image of edge gain under an anti-involution. In this paper, we deal with the adjacency matrix of skew gain graphs with an involutive automorphism on a field of characteristic zero and their characteristic polynomials. Spectra of some particular skew gain graphs are also discussed. [ABSTRACT FROM AUTHOR]

It was shown in 2006 that among the nonsingular trees T (whose adjacency matrix A(T) is nonsingular), the corona trees (trees that are obtained by taking any tree T and then adding a new pendant vertex at each vertex of T) are the only ones which satisfy the reciprocal eigenvalue property (λ is an eigenvalue of A(T) if and only if 1 λ is an eigenvalue of A(T), where their multiplicities are allowed to be different). A general question remained open. Can there be a tree which has at least one zero eigenvalue and whose nonzero eigenvalues satisfy the reciprocal eigenvalue property? In this note, we show that there are no such trees with at least two vertices. The proof is a beautiful application of the product of graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be its adjacency matrix. The terms singularity, eigenvalues, and characteristic polynomial of G mean those of A (G). A nonsingular graph G is said to have the reciprocal eigenvalue property if the reciprocal of each eigenvalue of G is also an eigenvalue. A graph G (possibly singular) is said to have the weak reciprocal eigenvalue property if the reciprocal of each nonzero eigenvalue of it is also an eigenvalue. In Barik et al. (2022) [3] , the authors proved that there is no nontrivial tree with the weak reciprocal eigenvalue property and posed the following question: "Does there exist a nontrivial graph with the weak reciprocal eigenvalue property?" Suppose that G is singular and the characteristic polynomial of G is x n − k (x k + a 1 x k − 1 + ⋯ + a k). Assume that A (G) has rank k , so that a k ≠ 0. Can we ever have | a k | = 1 ? The answer turns out to be negative. As an application, we settle the question posed in Barik et al. (2022) [3]. Another similar application is also mentioned. It is natural to wonder, "Does there exist a nontrivial, simple, connected weighted graph with the weak reciprocal eigenvalue property?" We provide a class of such graphs. Furthermore, we extend our results to weighted graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple graph and A(G) be its adjacency matrix. We say that the graph G satisfies reciprocal eigenvalue property (or simply, property (R)) if 1 λ is an eigenvalue of A(G), whenever λ is an eigenvalue of A(G). The graph G satisfies strong anti-reciprocal property (or simply, property (-SR)) if - 1 λ is an eigenvalue of A(G) with multiplicity k, whenever λ is an eigenvalue of A(G) with multiplicity k. Recently, Barik, Mondal and Pati proved that there exists no singular (non-trivial) tree whose nonzero eigenvalues satisfy reciprocal eigenvalue property. As a concluding remark, the authors mentioned that "It is interesting to see that our result (for trees) is true for any connected graph". In this paper, we prove that there exists no singular unicyclic graph whose nonzero eigenvalues satisfy reciprocal eigenvalue property. Ahmad, Hameed and Jabeen in their recent paper raised the question about existence of noncorona graphs with property (-SR) and constructed seven classes of graphs satisfying this property. Here, we give several families of noncorona graphs with property (-SR). [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]

Given a combinatorially symmetric matrix A whose graph is a tree T and its eigenvalues, edges in T can be classified in four categories, based upon the change in geometric multiplicity of a particular eigenvalue, when the edge is removed. We investigate a necessary and sufficient condition for each classification of edges. We have similar results as the case for real symmetric matrices whose graph is a tree. We show that a g-2-Parter edge, a g-Parter edge and a g-downer edge are located separately from each other in a tree, and there is a g-neutral edge between them. Furthermore, we show that the distance between a g-downer edge and a g-2-Parter edge or a g-Parter edge is at least 2 in a tree. Lastly we give a combinatorially symmetric matrix whose graph contains all types of edges.

We investigate the change in the multiplicities of an eigenvalue of an Hermitian matrix whose graph is a general undirected graph, when an edge is removed from the graph. The same question when the graph is a tree has been investigated in prior work. Here, we give possible classifications of edges in a general graph in terms of the statuses of adjacent vertices. It turns out that there are four cases that do occur in a general graph but cannot occur in a tree. [ABSTRACT FROM AUTHOR]

Let G be a simple 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 signless Laplacian matrix of G is Q (G) = D (G) + A (G). Let q 1 ≥ q 2 ≥ ⋯ ≥ q n be the signless Laplacian eigenvalues of graph G and also let ν = ν (G) (1 ≤ ν ≤ n) be the largest positive integer such that q ν ≥ 2 m / n . Denote by G ¯ the complement graph of graph G. If G ≆ K n , K ¯ n , K n − 1 ∪ K 1 , K 1 , n − 1 , K n − e , K 2 ∪ (n − 2) K 1 , then we prove that q 2 (G) + q 2 (G ¯) ≥ n − 1. Moreover, if G ≆ K 1 , n − 1 , K n − 1 ∪ K 1 , K n − e , K 2 ∪ (n − 2) K 1 , then ν + ν ¯ ≥ 3. [ABSTRACT FROM AUTHOR]

The aim of this note is to provide an interpretation of two families of quasi anti-tridiagonal matrices in terms of graph theory. Understanding this junction allows us to recover a plethora of recent results on spectra, powers, inverse problems, and determinant, among others, of such matrices. [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]

The spectral radius ρ (G) of a graph G is the largest eigenvalue of its adjacency matrix A (G). In this paper, we first give a sharp lower bound of the spectral radius of a graph G in terms of the degree and the average 2-degree which generalizes a result of Das and Kumar (2003), and then as an application, a sharp upper bound of the energy of G is given which generalizes a result of Liu et al. (2007). [ABSTRACT FROM AUTHOR]

A matrix A is said to be an integer matrix if all its entries are integers. In this article, we characterize the nonsingular integer matrices with integer eigenvalues in an expressible form of their corresponding inverse matrices. It is proved that a nonsingular integer matrix A has integer eigenvalues if and only if A − 1 can be written as the sum of n rank-one matrices that meet certain requirements. A method for constructing integer matrices with integer eigenvalues using the Hadamard product is also provided. Let S represent an n -tuple of nonnegative integers. If there is an n × n integer matrix A whose spectrum (the collection of eigenvalues) is S , we say that S is realisable by an integer matrix. In Fallat et al. (2005) [7] , the authors posed a conjecture that " there is no simple graph on n ≥ 2 vertices whose Laplacian spectrum is given by (0 , 1 , ... , n − 1)." We provide a characterization of threshold graphs using the spectra of quotient matrices of its G -join graphs. As a consequence, we prove that given any n − 1 positive integers λ 2 , ... , λ n such that λ 2 ≤ ⋯ ≤ λ n , the n -tuple (0 , λ 2 , ... , λ n) is realizable by the Laplacian matrix of a multidigraph. In particular, we show that (0 , 1 , ... , n − 1) can be realizable by the Laplacian matrix of a multidigraph. [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]

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]

Gain graphs are graphs where the edges are given some orientation and labeled with the elements (called gains) from a group so that gains are inverted when we reverse the direction of the edges. Generalizing the notion of gain graphs, skew gain graphs have the property that the gain of a reversed edge is the image of edge gain under an anti-involution. In this paper, we study two different types, Laplacian and g-Laplacian matrices for a skew gain graph where the skew gains are taken from the multiplicative group Fx of a field F of characteristic zero. Defining incidence matrix, we also prove the matrix tree theorem for skew gain graphs in the case of the g-Laplacian matrix. [ABSTRACT FROM AUTHOR]

The location of the nontrivial poles of a generalized zeta function is derived from the spectrum of Ramanujan graphs and bounds are established for irregular graphs. The existence of a similarity transformation of the diagonal matrix given by a specified set of eigenvalues to an adjacency matrix of a graph is proven, and the method yields a set of finite graphs with eigenvalues determined approximately by a finite subset of the poles of the Ihara zeta function.

Given a regular (connected) graph Γ = (X, E) with adjacency matrix A, d+1 distinct eigenvalues, and diameter D, we give a characterization of when its distance matrix AD is a polynomial in A, in terms of the adjacency spectrum of Γ and the arithmetic (or harmonic) mean of the numbers of vertices at distance at most D − 1 from every vertex. The same result is proved for any graph by using its Laplacian matrix L and corresponding spectrum. When D = d we reobtain the spectral excess theorem characterizing distance-regular graphs. [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]

We take as given a real symmetric matrix A, whose graph is a tree T, and the eigenvalues of A, with their multiplicities. Each edge of T may then be classified in one of four categories, based upon the change in multiplicity of a particular eigenvalue, when the edge is removed (i.e. the corresponding entry of A is replaced by 0).We show a necessary and suficient condition for each possible classification of an edge. A special relationship is observed among 2-Parter edges, Parter edges and singly Parter vertices. Then, we investigate the change in multiplicity of an eigenvalue based upon a change in an edge value. We show how the multiplicity of the eigenvalue changes depending upon the status of the edge and the edge value. This work explains why, in some cases, edge values have no effect on multiplicities. We also characterize, more precisely, how multiplicity changes with the removal of two adjacent vertices.

Suppose that the vertex set of a graph G is V(G) = {v1, v2,..., vn}. The transmission Tr(vi) (or Di) of vertex vi is defined to be the sum of distances from vi to all other vertices. Let Tr(G) be the n × n diagonal matrix with its (i, i)-entry equal to TrG(vi). The distance signless Laplacian spectral radius of a connected graph G is the spectral radius of the distance signless Laplacian matrix of G, defined as Q (G) = Tr (G) + D (G) , where D(G) is the distance matrix of G. In this paper, we give a lower bound on the distance signless Laplacian spectral radius of graphs and characterize graphs for which these bounds are best possible. We obtain a lower bound on the second largest distance signless Laplacian eigenvalue of graphs. Moreover, we present lower bounds on the spread of distance signless Laplacian matrix of graphs and trees, and characterize extremal 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 Let G = (V , E) be a simple graph of order n with normalized Laplacian eigenvalues ρ 1 ≥ ρ 2 ≥ ⋯ ≥ ρ n − 1 ≥ ρ n = 0. The normalized Laplacian spread of graph G , denoted by ρ 1 − ρ n − 1 , is the difference between the largest and the second smallest normalized Laplacian eigenvalues of graph G. In this paper, we obtain the first four smallest values on ρ 2 of graphs. Moreover, we give a lower bound on ρ 2 of connected bipartite graph G except the complete bipartite graph and characterize graphs for which the bound is attained. Finally, we present some bounds on the normalized Laplacian spread of graphs and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

This work is dedicated to the solution of direct and inverse spectral problems for Sturm-Liouville differential operators on star-shaped graphs with n+1 edges; n edges are finite, and one edge is infinite. Eigenvalues visible at infinity, eigenvalues invisible at infinity and resonances of this spectral problem are found. It is shown that the problem of determining n unknown coeffcients of boundary conditions by n eigenvalues visible at infinity and (or) resonances has n! solutions. If the finite edges of the graph are equal in length, then the boundary conditions are determined up to a permutation of the fastening ends. It is proved that the boundary conditions are uniquely determined up to permutations on the dead-end vertices by resonances. If 2n + 1 eigenvalues visible at infinity and (or) resonances are used to reconstruct the boundary conditions (2n unknown coeffcients), then the identification problem of the boundary conditions has n! solutions. If the finite edges of the graph are equal in length, then the boundary conditions are uniquely determined up to permutations on the dead-end vertices. [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]

We are interested in the geometric multiplicity of an identified eigenvalue of a matrix A over a general field with a given graph G for its off-diagonal entries. By the classification of a vertex (edge) of G, we refer to the change in the geometric multiplicity of when this vertex (edge) is removed from G to leave a principal submatrix (modification) of A. Such classification in the case of Hermitian matrices and trees has been strategic in the problem of determining the possible lists of multiplicities for the eigenvalues among matrices with the given graph. Here, our view of, and qualification of, the classification in the general setting provides a tool that makes some past arguments more transparent and provides new insight in both the classical and general setting. Some applications are given to general downer mechanisms for the recognition of Parter vertices and to the stability of geometric multiplicity under perturbation of a diagonal entry. [ABSTRACT FROM AUTHOR]

In this article, we introduce a Laplacian for the reciprocal distance matrix of a connected graph, called the reciprocal distance Laplacian. Let δ1≥δ2≥⋯≥δn-1≥δn be the reciprocal distance Laplacian spectrum. In this short note, we show that δ1≤n with equality if and only if the complement graph G¯ of G is disconnected. [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]

For any prime p let Cp(G) be the p-ary code spanned by the rows of the incidence matrix G of a graph Γ. Let Γ be the incidence graph of a flag-transitive symmetric design D. We show that any flag-transitive automorphism group of D can be used as a PD-set for full error correction for the linear code Cp(G) (with any information set). It follows that such codes derived from flag-transitive symmetric designs can be decoded using permutation decoding. In that way to each flag-transitive symmetric (v,k,λ) design we associate a linear code of length vk that is permutation decodable. PD-sets obtained in the described way are usually of large cardinality. By studying codes arising from some flag-transitive symmetric designs we show that smaller PD-sets can be found for specific information sets. [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]

Let G=(V,E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the Laplacian matrix and the signless Laplacian matrix of G are L(G)=D(G)-A(G) and Q(G)=D(G)+A(G), respectively. Also denote by λ1(G), a(G), q1(G) and δ(G) the largest eigenvalue of A(G), the second smallest eigenvalue of L(G), the largest eigenvalue of Q(G) and the minimum degree of G, respectively. In this paper, we give partial proofs to the following two conjectures: (i)Aouchiche (Comparaison Automatisée d’Invariants en Théorie des Graphes, 2006) if G is a connected graph, then a(G)/δ(G) is minimum for graph composed of 2 triangles linked with a path. (ii)Aouchiche et al. (Linear Algebra Appl 432:2293-2322, 2010) and Cvetković et al. (Publ Inst Math Beogr 81(95):11-27, 2007) if G is a connected graph with n≥4 vertices, then q1(G)-2λ1(G)≤n-2n-1 with equality holding if and only if G≅K1,n-1. [ABSTRACT FROM AUTHOR]

Finding all the graphs with a certain number of Q -main eigenvalues is an algebraic graph theory problem that scientists have sought to answer it for many years. The purpose of this research is finding relationships between the algebraic properties of a signless Laplacian matrix of a graph and the other properties of that graph. In order to achieve this, we choose to characterize all the unicyclic and bicyclic graphs with exactly three distinct Q -main eigenvalues, one of which is zero. [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]