Search

A mixed graph is obtained from a graph by orienting some of its edges. The Hermitian adjacency matrix of a mixed graph with the vertex set { v 1 , ... , v n } , is the matrix H = h i j n × n , where h i j = − h j i = i if there is a directed edge from v i to v j , h i j = 1 if there exists an undirected edge between v i and v j , and h i j = 0 otherwise. The Hermitian spectrum of a mixed graph is defined to be the spectrum of its Hermitian adjacency matrix. In this paper we study mixed graphs which are determined by their Hermitian spectrum (DHS). First, we show that each mixed cycle is switching equivalent to either a mixed cycle with no directed edges (C n), a mixed cycle with exactly one directed edge (C n 1), or a mixed cycle with exactly two consecutive directed edges with the same direction (C n 2) and we determine the spectrum of these three types of cycles. Next, we characterize all DHS mixed paths and mixed cycles. We show that all mixed paths of even order, except P 8 and P 14 , are DHS. It is also shown that mixed paths of odd order, except P 3 , are not DHS. Also, all cospectral mates of P 8 , P 14 and P 4 k + 1 and two families of cospectral mates of P 4 k + 3 , where k ≥ 1 , are introduced. Finally, we show that the mixed cycles C 2 k and C 2 k 2 , where k ≥ 3 , are not DHS, but the mixed cycles C 4 , C 4 2 , C 2 k + 1 , C 2 k + 1 2 , C 2 k + 1 1 and C 2 j 1 except C 7 1 , C 9 1 , C 12 1 and C 15 1 , are DHS, where k ≥ 1 and j ≥ 2. [ABSTRACT FROM AUTHOR]

For a given connected (undirected) graph G = ( V , E ) , with V = { 1 , … , n } , the minimum rank of G is defined to be the smallest possible rank over all symmetric matrices A = [ a i j ] such that for i ≠ j , a i j = 0 if, and only if, { i , j } ∉ E . The path cover number of G is the minimum number of vertex-disjoint paths occurring as induced subgraphs of G that cover all the vertices of G . When G is a tree, the values of the minimum rank and of the path cover number are known as well the relationship between them. We study these values and their relationship for all graphs that have at most two vertices of degree greater than two: generalized cycle stars and double generalized cycle stars. [ABSTRACT FROM AUTHOR]

Let G be a k -connected irregular graph with n vertices, m edges, maximum degree Δ and minimum degree δ . In this paper, we mainly show 2 Δ − q 1 ( G ) > 2 ( n Δ − 2 m ) k 2 2 ( n Δ − 2 m ) [ ( n − 2 + 2 k − Δ ) ( n − δ − 1 ) + k 2 ] + n k 2 , where q 1 ( G ) is the signless Laplacian spectral radius of G . The inequality improves previous bounds of several authors in some cases. It also implies a lower bound of 2 Δ − q 1 ( H ) for a proper subgraph H of a k -connected Δ-regular graph. Another lower bound of 2 Δ − q 1 ( G ) for a connected graph G is also given. [ABSTRACT FROM AUTHOR]

A graph is called a threshold graph if it does not contain induced C 4 , P 4 or 2 K 2 . Such graphs have numerous applications in computer science and psychology, and they also have nice spectral properties. In this paper, we consider the distance matrix of a connected threshold graph. We show that there are no distance eigenvalues of threshold graphs lying in the interval ( − 2 , − 1 ) and all the eigenvalues, other than −2 or −1, are simple. Besides, we determine all threshold graphs with distinct distance eigenvalues. [ABSTRACT FROM AUTHOR]

A signed graph is a pair like ( G , σ ) , where G is the underlying graph and σ : E ( G ) → { − 1 , + 1 } is a sign function on the edges of G . In this paper we study the spectral determination problem for signed n -cycles ( C n , σ ) with respect to the adjacency spectrum and the Laplacian spectrum. In particular, for the Laplacian spectrum, we prove that balanced odd cycles and unbalanced cycles, denoted, respectively, by C 2 n + 1 + and C n − , are uniquely determined by their Laplacian spectra (i.e., they are DLS). On the other hand, we determine all Laplacian cospectral mates of the balanced even cycles C 2 n + , so that we show that C 2 n + is not DLS. The same problem is then considered for the adjacency spectrum, hence we prove that odd signed cycles, namely, C 2 n + 1 + and C 2 n + 1 − , are uniquely determined by their (adjacency) spectrum (i.e., they are DS). Moreover, we find cospectral mates for the even signed cycles C 2 n + and C 2 n − , and we show that, except the signed cycle C 4 − , even signed cycles are not DS and we provide almost all cospectral mates. [ABSTRACT FROM AUTHOR]

The distance matrix, distance eigenvalue, and distance energy of a connected graph have been studied intensively in the literature. We propose a new problem of studying how the distance energy changes when an edge is deleted. In this paper, we prove that the distance energy of a complete bipartite graph is always increased when an edge is deleted. [ABSTRACT FROM AUTHOR]

A sequential dynamical system (SDS) consists of a graph, a set of local functions and an update schedule. A linear sequential dynamical system is an SDS whose local functions are linear. In this paper, we derive an explicit closed formula for any linear SDS as a synchronous dynamical system. We also show constructively, that any synchronous linear system can be expressed as a linear SDS, i.e. it can be written as a product of linear local functions. Furthermore, we study the connection between linear SDS and the incidence algebras of partially ordered sets (posets). Specifically, we show that the Möbius function of any poset can be computed via an SDS, whose graph is induced by the Hasse diagram of the poset. Finally, we prove a cut theorem for the Möbius functions of posets with respect to certain chain decompositions. [ABSTRACT FROM AUTHOR]

We prove that det ⁡ A ≤ 6 n 6 whenever A ∈ { 0 , 1 } n × n contains at most 2 n ones. We also prove an upper bound on the determinant of matrices with the k -consecutive ones property, a generalisation of the consecutive ones property, where each row is allowed to have up to k blocks of ones. Finally, we prove an upper bound on the determinant of a path-edge incidence matrix in a tree and use that to bound the leaf rank of a graph in terms of its order. [ABSTRACT FROM AUTHOR]

A signed graph Γ is said to be determined by its spectrum if every signed graph with the same spectrum as Γ is switching isomorphic with Γ. Here it is proved that the path P n , interpreted as a signed graph, is determined by its spectrum if and only if n ≡ 0 , 1 , or 2 (mod 4), unless n ∈ { 8 , 13 , 14 , 17 , 29 } , or n = 3 . [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices, and let d i be the degree of its i -th vertex. The ABC matrix of G is the square matrix of order n whose ( i , j ) -entry is equal to ( d i + d j − 2 ) / ( d i d j ) if the i -th vertex and the j -th vertex of G are adjacent, and 0 otherwise. This matrix, related closely to the atom-bond connectivity (abbreviated as ABC ) index, was recently introduced by Estrada as a matrix representation of the probability of visiting a nearest neighbor edge from one side or the other of a given edge in a graph, which in the context of molecular graphs can be related to the polarizing capacity of the bond considered. The ABC eigenvalues of G are the eigenvalues of its ABC matrix, and the ABC energy of G is the sum of the absolute values of its ABC eigenvalues. In this paper, some new results for the ABC eigenvalues and the ABC energy of a graph are presented. [ABSTRACT FROM AUTHOR]

Let G = ( V ( G ) , E ( G ) ) be an ( n , m ) -graph. The Randić spread of G , s R ( G ) , is defined as the maximum distance of its Randić eigenvalues, disregarding the Randić spectral radius of G . In this work, we use numerical inequalities and bounds for the matricial spread to obtain relations between this spectral parameter and some structural and algebraic parameters of the underlying graph such as, the sequence of vertex degrees, the nullity, Randić index, generalized Randić indices and its independence number. In the last section a comparison is presented for regular graphs. [ABSTRACT FROM AUTHOR]

Let Γ = ( G , σ ) be a signed graph and A ( Γ ) be its adjacency matrix, where G is the underlying graph of Γ. The rank r ( Γ ) of Γ is the rank of A ( Γ ) . We know that for a signed graph Γ = ( G , σ ) , Γ is balanced if and only if Γ = ( G , σ ) ∼ ( G , + ) . That is, when Γ is balanced, then r ( Γ ) = r ( G ) , where r ( G ) is the rank of the underlying graph G of Γ. A natural problem is that: how about the relations between the rank of an unbalanced signed graph and the rank of its underlying graph? In this paper, we first prove that r ( G ) − 2 d ( G ) ≤ r ( Γ ) ≤ r ( G ) + 2 d ( G ) for an unbalanced signed graph with d ( G ) ≥ 1 , where d ( G ) = | E ( G ) | − | V ( G ) | + ω ( G ) is the dimension of cycle spaces of G , ω ( G ) is the number of connected components of G . As an application, we also prove that 1 − d ( G ) < r ( Γ ) r ( G ) ≤ 1 + d ( G ) for an unbalanced signed graph with d ( G ) ≥ 1 . All corresponding extremal graphs are characterized. [ABSTRACT FROM AUTHOR]

In this paper, we study the least Q-eigenvalue of a non-bipartite hamiltonian graph, and determine all non-bipartite hamiltonian graphs whose least Q-eigenvalue attains the minimum among all non-bipartite hamiltonian graphs on n vertices. [ABSTRACT FROM AUTHOR]

Arithmetical structures on a graph were introduced by Lorenzini in [9] as some intersection matrices that arise in the study of degenerating curves in algebraic geometry. In this article we study these arithmetical structures, in particular we are interested in the arithmetical structures on complete graphs, paths, and cycles. We begin by looking at the arithmetical structures on a multidigraph from the general perspective of M -matrices. As an application, we recover the result of Lorenzini about the finiteness of the number of arithmetical structures on a graph. We give a description on the arithmetical structures on the graph obtained by merging and splitting a vertex of a graph in terms of its arithmetical structures. On the other hand, we give a description of the arithmetical structures on the clique–star transform of a graph, which generalizes the subdivision of a graph. As an application of this result we obtain an explicit description of all the arithmetical structures on the paths and cycles and we show that the number of the arithmetical structures on a path is a Catalan number. [ABSTRACT FROM AUTHOR]

A rose graph is a graph consisting of cycles that all meet in one vertex. We show that except for two specific examples, these rose graphs are determined by the Laplacian spectrum, thus proving a conjecture posed by Liu and Huang (2013) [8] . We also show that if two rose graphs have a so-called universal Laplacian matrix with the same spectrum, then they must be isomorphic. In memory of Horst Sachs (1927–2016), we show the specific case of the latter result for the adjacency matrix by using Sachs' theorem and a new result on the number of matchings in the disjoint union of paths. [ABSTRACT FROM AUTHOR]

The reconstruction problem of the characteristic polynomial of graphs from their polynomial decks was posed in 1973. So far this problem is not resolved except for some particular cases. Moreover, no counterexample for graphs of order n > 2 is known. Here we put forward the analogous problem for signed graphs, and besides some general results, we resolve it within signed trees and unicyclic signed graphs, and also within disconnected signed graphs whose one component is either a signed tree or is unicyclic. A family of counterexamples that was encountered in this paper consists of two signed cycles of the same order, one balanced and the other unbalanced. [ABSTRACT FROM AUTHOR]

In this paper, we give a sufficient condition on the spectral radius for a graph to be Hamiltonian. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to study spectral properties of a family of Cayley graphs on finite commutative rings. Let R be such a ring and R × be its set of units. Let Q R = { u 2 : u ∈ R × } and T R = Q R ∪ ( − Q R ) . We define the quadratic unitary Cayley graph of R , denoted by G R , to be the Cayley graph on the additive group of R with respect to T R ; that is, G R has vertex set R such that x , y ∈ R are adjacent if and only if x − y ∈ T R . It is well known that any finite commutative ring R can be decomposed as R = R 1 × R 2 × ⋯ × R s , where each R i is a local ring with maximal ideal M i . Let R 0 be a local ring with maximal ideal M 0 such that | R 0 | / | M 0 | ≡ 3 ( mod 4 ) . We determine the spectra of G R and G R 0 × R under the condition that | R i | / | M i | ≡ 1 ( mod 4 ) for 1 ≤ i ≤ s . We compute the energies and spectral moments of such quadratic unitary Cayley graphs, and determine when such a graph is hyperenergetic or Ramanujan. [ABSTRACT FROM AUTHOR]

Let G be a graph with maximum degree Δ, and let G σ be an oriented graph of G with skew adjacency matrix S ( G σ ) . The skew spectral radius ρ s ( G σ ) of G σ is defined as the spectral radius of S ( G σ ) . The skew spectral radius has been studied, but only few results about its lower bound are known. This paper determines some lower bounds of the skew spectral radius, and then studies the oriented graphs whose skew spectral radii attain the lower bound Δ . Moreover, we apply the skew spectral radius to the skew energy of oriented graphs, which is defined as the sum of the norms of all the eigenvalues of S ( G σ ) , and denoted by E s ( G σ ) . As a result, we obtain some lower bounds of the skew energy, which improve the known lower bound obtained by Adiga et al. [ABSTRACT FROM AUTHOR]

We consider the problem of determining those undirected n -vertex graphs with a corresponding Hermitian matrix that admits only two distinct eigenvalues, with multiplicities k and n--k. After giving some general algebraic characterizations of these dual multiplicity graphs, we then prove two major graph theoretic necessary conditions on such graphs. Construction techniques are then developed, and these lead to a characterization of dual multiplicity graphs for which the lesser multiplicity is two. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with order n and D(G) be the distance matrix of G. Suppose that λ1(D)≥λ2(D)≥⋯≥λn(D) are the D-eigenvalue of G. In this paper, we show that λn-1(D(G))≤-1 if n≥4 and λn-2(D(G))≤-1 if n≥7. We also characterize all connected graphs with λn-1(D(G))=-1, moreover it is shown that these graphs are determined by their distance spectra. [ABSTRACT FROM AUTHOR]

Let N be a positive integer and R(N,N) denote the Ramsey number (see [15] or [11]) such that any graph with at least R(N,N) vertices contains a clique with N vertices or an independent set with N vertices. We show that any graph G with order at least R(N,N) must have its Nth largest eigenvalue λN(G)≥-1, and that any graph G with order at least R(N+1,N+1) must have its Nth smallest eigenvalue λN'(G)≤0, where the bounds -1 and 0 are best possible. This reveals some connection between graph spectra and Ramsey numbers, and enables us to give bounds of some eigenvalues for graphs with order greater than certain numbers. Moreover, it leads to a disproof of a conjecture on limit points of graph eigenvalues posted by Cao and Yuan [3] in 1995. [ABSTRACT FROM AUTHOR]

The notion of walk entropy SV(G,β) for a graph G at the inverse temperature β was put forward recently by Estrada et al. (2014) [7]. It was further proved by Benzi [1] that a graph is walk-regular if and only if its walk entropy is maximum for all temperatures β∈I, where I is a set of real numbers containing at least an accumulation point. Benzi [1] conjectured that walk regularity can be characterized by the walk entropy if and only if there is a β>0 such that SV(G,β) is maximum. Here we prove that a graph is walk regular if and only if the SV(G,β=1)=lnn. We also prove that if the graph is regular but not walk-regular SV(G,β)0 and limβ→0SV(G,β)=lnn=limβ→∞SV(G,β). If the graph is not regular then SV(G,β)≤lnn-ϵ for every β>0, for some ϵ>0. [ABSTRACT FROM AUTHOR]

In this paper, we characterize all similarity relations when m≥3, obtain some interesting properties which are different from the matrix case (m=2), and show that some of the well-known results of matrices cannot be extended to tensors of order m≥3 . [ABSTRACT FROM AUTHOR]

The subdivision graph S(G) of a graph G is the graph obtained by inserting a new vertex into every edge of G. Let G1∪G2 be the disjoint union of two graphs G1 and G2 . The subdivision-vertex join of G1 and G2, denoted by G1∨G2, is the graph obtained from S(G1)∪G2 by joining every vertex in V(G1) to every vertex in V(G2) . The subdivision-edge join of G1 and G2, denoted by G1⊻G2, is the graph obtained from S(G1)∪G2 by joining every vertex in I(G1) to every vertex in V(G2), where I(G1) is the set of inserted vertices of S(G1) . In this paper, formulae for resistance distance in G1∨G2 and G1⊻G2 are obtained. [ABSTRACT FROM AUTHOR]

Several approaches for ordering graphs by spectral parameters are presented in the literature. We can find graph orderings either by the greatest eigenvalue (spectral radius or index) or by the sum of the absolute values of the eigenvalues (the energy of a graph) or by the second smallest eigenvalue of the Laplacian matrix (the algebraic connectivity), among others. By considering the fact that the algebraic connectivity is related to the connectivity and shape of the graphs, several structural properties of graphs relative to this parameter have been studied. Hence, a large number of papers about ordering graphs by algebraic connectivity, mainly about trees and graphs with few cycles, have been published. This paper surveys the significant results concerning these topics, trying to focus on possible points to be investigated in order to understand the difficulties to obtain partial orderings via algebraic connectivity. [ABSTRACT FROM AUTHOR]

Let q(G) be the Q-index (the largest eigenvalue of the signless Laplacian) of G. Let Sn,k be the graph obtained by joining each vertex of a complete graph of order k to each vertex of an independent set of order n-k. The main result of this paper is the following theorem: Let k≥3, n≥110k², and G be a graph of order n. If G has no C2k+1, then q(G)

Let G be a bipartite graph with μ as an eigenvalue of multiplicity k>1. We show that if G has Kr,s(1≤r≤s) as a star complement for μ then k≤s-1; moreover if μ is non-main then k≤s-2 for large enough s. We provide examples of graphs in which various bounds on k or s are attained. We also describe the bipartite graphs with K1,s as a star complement for a non-main eigenvalue of multiplicity s-1>1. [ABSTRACT FROM AUTHOR]

In 1971, Graham and Pollack established a relationship between the number of negative eigenvalues of the distance matrix and the addressing problem in data communication systems. They also proved that the determinant of the distance matrix of a tree is a function of the number of vertices only. Since then several mathematicians were interested in studying the spectral properties of the distance matrix of a connected graph. Computing the distance characteristic polynomial and its coefficients was the first research subject of interest. Thereafter, the eigenvalues attracted much more attention. In the present paper, we report on the results related to the distance matrix of a graph and its spectral properties. [ABSTRACT FROM AUTHOR]

Let τ (G) and λ2(G) be the maximum number of edge-disjoint spanning trees and the second largest eigenvalue of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and τ (G), Cioabă and Wong conjectured that for any integers k ≥ 2, d ≥ 2k and a d-regular graph G, if λ2 (G)

The spectral excess theorem states that, in a regular graph Γ, the average excess, which is the mean of the numbers of vertices at maximum distance from a vertex, is bounded above by the spectral excess (a number that is computed by using the adjacency spectrum of Γ), and Γ is distance-regular if and only if equality holds. In this note we prove the corresponding result by using the Laplacian spectrum without requiring regularity of Γ. [ABSTRACT FROM AUTHOR]

We consider the direct product of a complete graph with K2 and present a direct construction for minimum cycle basis of this graph. We show that this basis is weakly fundamental. We also construct a minimum fundamental cycle basis of this graph. Moreover, we characterize all trees which give a minimum fundamental cycle basis of this graph [ABSTRACT FROM AUTHOR]