Search

Let T be the multiplicative group of complex units, and let L(Φ) denote the Laplacian matrix of a nonempty T-gain graph Φ=(Γ,T,γ). The gain line graph L(Φ) and the gain subdivision graph S(Φ) are defined up to switching equivalence. We discuss how the eigenspaces determined by the adjacency eigenvalues of L(Φ) and S(Φ) are related with those of L(Φ). [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]

Let Γ = (G , σ) be a signed graph. The spectral radius of Γ is the largest absolute value of its adjacency eigenvalues. In this paper we identify the real numbers which are limit points of spectral radii of signed graphs. This is one of the two aspects of a problem in spectral graph theory known as the Hoffman program, implemented here for signed graphs. [ABSTRACT FROM AUTHOR]

Let T4 = {±1, ±i} be the subgroup of 4-th roots of unity inside T, the multiplicative group of complex units. A complex unit gain graph Φ is a simple graph Γ = (V(Γ) = {v1,..., vn},E(Γ)) equipped with a map φ: E (Γ) → T defined on the set of oriented edges such that φ(vivj) = φ(vj vi)-1. The gain graph Φ is said to be balanced if for every cycle C = vi1 vi2 ... vik vi1 we have φ(vi1 vi2) φ(vi2vi3) ... φ(vikvi1) = 1. It is known that Φ is balanced if and only if the least Laplacian eigenvalue λn(Φ) is 0. Here we show that, if Φ is unbalanced and £(Φ) ⊆ T4, the eigenvalue λn(Φ) measures how far is Φ from being balanced. More precisely, let v(Φ) (respectively, ∊(Φ)) be the number of vertices (respectively, edges) to cancel in order to get a balanced gain subgraph. We show that λn(Φ) ≤ V(Φ) ≤ ∊(Φ). We also analyze the case when λn(Φ) = v(Φ). In fact, we identify the structural conditions on Φ that lead to such equality. [ABSTRACT FROM AUTHOR]

A signed graph is a pair Γ = ( G , σ ) , where G = ( V ( G ) , E ( G ) ) is a graph and σ : E ( G ) → { + 1 , − 1 } is the sign function on the edges of G . For a signed graph we consider the Laplacian matrix defined as L ( Γ ) = D ( G ) − A ( Γ ) , where D ( G ) is the matrix of vertices degrees of G and A ( Γ ) is the (signed) adjacency matrix. The least Laplacian eigenvalue is zero if and only if the signed graph is balanced, i.e. all cycles contain an even number of negative edges. Here we show that among the unbalanced bicyclic signed graphs of given order n ≥ 5 the least Laplacian eigenvalue is minimal for signed graphs consisting of two triangles, only one of which is unbalanced, connected by a path. We also identify the signed graphs minimizing the least eigenvalue among those whose unbalanced (bicyclic) base is a theta-graph. [ABSTRACT FROM AUTHOR]

Letbe a signed graph, whereGis the underlying graph andis the signature function on the edges ofG. In this paper, we consider the Laplacian eigenvalues of signed graphs and we characterize the connected signed graphs whose second largest Laplacian eigenvalue does not exceed 3. Furthermore, we study the Laplacian spectral determination of most graphs in the latter family. [ABSTRACT FROM AUTHOR]

Graphs with least eigenvalue greater than or equal toare to a big extent studied by Hoffman and other authors from the early beginning of the spectral graph theory. Most of these results are summarized in the monograph [Cvetković D, Rowlinson P, Simić S. Spectral generalizations of line graphs, on graphs with least eigenvalue, Cambridge University Press, 2004], and the survey paper [Cvetković D, Rowlinson P, Simić S. Graphs with least eigenvalue: ten years on, Linear Algebra Appl. 2015;484:504–539] which is aimed to cover the next 10 years since their monograph appeared. Here, we add some further results. Among others, we identify graphs whose least eigenvalue is greater than, but closest towithin the graphs of fixed order. Some consequences of these considerations are found in the context of the highest occupied molecular orbital–lowest unoccupied molecular orbital invariants. [ABSTRACT FROM AUTHOR]

We use star complement technique to construct a basis for − 2 of signed line graphs using their root signed graphs. In other words, we offer a generalization of the corresponding results known in the literature for (unsigned) graphs in the context of line graphs and generalized line graphs. [ABSTRACT FROM AUTHOR]

A signed graph is a pair Γ = ( G , σ ) , where G = ( V ( G ) , E ( G ) ) is a graph and σ : E ( G ) → { + , − } is the corresponding sign function. For a signed graph we consider the Laplacian matrix defined as L ( Γ ) = D ( G ) − A ( Γ ) , where D ( G ) is the matrix of vertex degrees of G and A ( Γ ) is the (signed) adjacency matrix. It is well-known that Γ is balanced, that is, each cycle contains an even number of negative edges, if and only if the least Laplacian eigenvalue λ n = 0 . Therefore, if Γ is not balanced, then λ n > 0 . We show here that among unbalanced connected signed graphs of given order the least eigenvalue is minimal for an unbalanced triangle with a hanging path, while the least eigenvalue is maximal for the complete graph with the all-negative sign function. [ABSTRACT FROM AUTHOR]

A simple connected non-regular graph is said to be-bidegreed, or biregular, if the vertices have degree from the set, with. We consider two classes of-bidegreed graphs denoted byand. A graph belongs toif: a) it is obtained fromdisjoint paths,, by identifying the verticesand the vertices, and the graph so obtained hasnvertices; b) for each of thenvertices, pendant vertices are added, so that any vertex from anyhas degree. The class,, is similarly obtained by identifying all the verticesandfrom the’s, into a single vertex. In this paper, we show that for any graph inor, the spectral radius of the adjacency matrix increases whenever the difference between the lengths of any two’s increases. We also compute some bounds for the spectral radius when the lengths of the’s tend to infinity. Finally, we discuss about bicyclic-bidegreed graphs withndegreevertices minimizing the spectral radius. We prove that in most cases such graphs do not belong to. [ABSTRACT FROM AUTHOR]

Abstract: Let be a connected signed graph, where G is the underlying simple graph and is the sign function on the edges of G. Let , be the Laplacian of Γ and be its eigenvalues. It is well-known that a signed graph Γ is balanced if and only if . Here we show that, if Γ is unbalanced, then estimates how much Γ is far from being balanced. In particular, let (resp. ) be the frustration number (resp. frustration index), that is the minimum number of vertices (resp. edges) to be deleted such that the signed graph is balanced. Then we prove that Further we analyze the case when . In the latter setting, we identify the structure of the underlying graph G and we give an algebraic condition for which leads to the above equality. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the relation between the -spectrum and the structure of in terms of the circumference of . Exploiting this relation, we give a novel necessary condition for a graph to be Hamiltonian by means of its -spectrum. We also determine the graphs with exactly one or two -eigenvalues greater than or equal to and obtain all minimal forbidden subgraphs and maximal graphs, as induced subgraphs, with respect to the latter property. [Copyright &y& Elsevier]

Abstract: For a graph G, we here investigate its signless Laplacian matrix and the corresponding Q-eigenvalues. By considering the relation between the Q-spectrum and the circumference of G, we characterize all connected graphs with exactly three Q-eigenvalues at least two. [Copyright &y& Elsevier]

Abstract: For a graph matrix M, the Hoffman limit value is the limit (if it exists) of the largest eigenvalue (or, M-index, for short) of , where the graph is obtained by attaching a pendant edge to the cycle of length . In spectral graph theory, M is usually either the adjacency matrix A or the Laplacian matrix L or the signless Laplacian matrix Q. The exact values of and were first determined by Hoffman and Guo, respectively. Since is bipartite for odd n, we have . All graphs whose A-index is not greater than were completely described in the literature. In the present paper, we determine all graphs whose Q-index does not exceed . The results obtained are determinant to describe all graphs whose L-index is not greater then . This is done precisely in Wang et al. (in press) . [Copyright &y& Elsevier]

Abstract: In this paper, we consider the signless Laplacians of simple graphs and we give some eigenvalue inequalities. We first consider an interlacing theorem when a vertex is deleted. In particular, let be a graph obtained from graph G by deleting its vertex v and be the ith largest eigenvalue of the signless Laplacian of G, we show that . Next, we consider the third largest eigenvalue and we give a lower bound in terms of the third largest degree of the graph G. In particular, we prove that . Furthermore, we show that in several situations the latter bound can be increased to . [Copyright &y& Elsevier]

Abstract: In this paper, we first give an upper bound for the largest signless Laplacian eigenvalue of a graph and find all the extremal graphs. Secondly, we consider the second-largest signless Laplacian eigenvalue and we characterize the connected graphs whose second-largest signless Laplacian eigenvalue does not exceed 3. Furthermore, we give the signless Laplacian spectral characterization of the latter graphs. In particular, the well-known friendship graph is proved to be determined by the signless Laplacian spectrum. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we consider the trees with fixed order and diameter . Among these trees we identify those trees whose index is minimal. [Copyright &y& Elsevier]

Abstract: The index (or spectral radius) of a simple graph is the largest eigenvalue of its adjacency matrix. For connected graphs of fixed order and size the graphs with maximal index are not yet identified (in the general case). It is known (for a long time) that these graphs are nested split graphs (or threshold graphs). In this paper we use the eigenvector techniques for getting some new (lower and upper) bounds on the index of nested split graphs. Besides we give some computational results in order to compare these bounds. [Copyright &y& Elsevier]

Abstract: We consider the set of unicyclic graphs with prescribed degree sequence. In this set we determine the (unique) graph with the largest spectral radius (or index) with respect to the adjacency matrix. In addition, we give a conjecture about the (unique) graph with the largest index in the set of connected graphs with prescribed degree sequence. [Copyright &y& Elsevier]

Abstract: The index of a graph is the largest eigenvalue (or spectral radius) of its adjacency matrix. We consider the problem of ordering graphs by the index in the class of connected graphs with a fixed order n and index belonging to the interval . For any fixed n (provided that n is not too small), we order a significant portion of graphs whose indices are close to the end points of the above interval. [Copyright &y& Elsevier]

Abstract: We identify in some classes of unicyclic graphs (of fixed order and girth) those graphs whose index, i.e. the largest eigenvalue, is maximal. Besides, some (lower and upper) bounds on the indices of the graphs being considered are provided. [Copyright &y& Elsevier]

• We provide an algorithm specialized to the class of unbalanced unicyclic signed graphs. • The algorithm computes the number of eigenvalues lying in a given real interval. • The spectrum of bidegreed signed circular caterpillars is retrieved. A signed graph is a pair Γ = (G , σ) , where G is a graph, and σ : E (G) ⟶ { + 1 , − 1 } is a signature of the edges of G. A signed graph Γ is said to be unbalanced if there exists a cycle in Γ with an odd number of negatively signed edges. In this paper it is presented a linear time algorithm which computes the inertia indices of an unbalanced unicyclic signed graph. Additionally, the algorithm computes the number of eigenvalues in a given real interval by operating directly on the graph, so that the adjacency matrix is not needed explicitly. As an application, the algorithm is employed to check the integrality of some infinite families of unbalanced unicyclic graphs. In particular, the multiplicities of eigenvalues of signed circular caterpillars are studied, getting a geometric characterization of those which are non-singular and sufficient conditions for them to be non-integral. Finally, the algorithm is also used to retrieve the spectrum of bidegreed signed circular caterpillars, none of which turns out to be integral. [ABSTRACT FROM AUTHOR]

Abstract In this paper we introduce a new graph matrix, named the anti-adjacency matrix or eccentricity matrix, which is constructed from the distance matrix of a graph by keeping for each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping for each row and each column only the distances equal to 1. We show that the eccentricity matrix of trees is irreducible, and we investigate the relations between the eigenvalues of the adjacency and eccentricity matrices. Finally, we give some applications of this new matrix in terms of molecular descriptors, and we conclude by proposing some further research problems. [ABSTRACT FROM AUTHOR]

Abstract: Let and be respectively the adjacency matrix and the degree matrix of a graph . The signless Laplacian matrix of is defined as . The -spectrum of is the set of the eigenvalues together with their multiplicities of . The -index of is the maximum eigenvalue of . The possibilities for developing a spectral theory of graphs based on the signless Laplacian matrices were discussed by Cvetković et al. [D. Cvetković, P. Rowlinson, S.K. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (2007) 155–171]. In the latter paper the authors determine the graphs whose -index is in the interval . In this paper, we investigate some properties of -spectra of graphs, especially for the limit points of the -index. By using these results, we characterize respectively the structures of graphs whose the -index lies in the intervals , and , where . [Copyright &y& Elsevier]

Abstract: The index of a graph is the largest eigenvalue of its adjacency matrix. Among the trees with a fixed order and diameter, a graph with the maximal index is a caterpillar. In the set of caterpillars with a fixed order and diameter, or with a fixed degree sequence, we identify those whose index is maximal. [Copyright &y& Elsevier]

Abstract: In this paper we give two results concerning the signless Laplacian spectra of simple graphs. Firstly, we give a combinatorial expression for the fourth coefficient of the (signless Laplacian) characteristic polynomial of a graph. Secondly, we consider limit points for the (signless Laplacian) eigenvalues and we prove that each non-negative real number is a limit point for (signless Laplacian) eigenvalue of graphs. [Copyright &y& Elsevier]