Search

Abstract For a nonnegative symmetric weakly irreducible tensor, its spectral radius is an eigenvalue of the tensor corresponding to a unique positive eigenvector called the Perron vector. But including the Perron vector, it may have more than one eigenvector corresponding to the spectral radius. The projective eigenvariety of the tensor associated with the spectral radius is the set of the eigenvectors of the tensor corresponding to the spectral radius considered in the complex projective space. In this paper we proved that such projective eigenvariety admits a module structure, which is determined by the support of the tensor and can be characterized explicitly by the Smith normal form of the incidence matrix of the tensor. We introduced two parameters: the stabilizing index and the stabilizing dimension of the tensor, where the former is exactly the cardinality of the projective eigenvariety and the latter is the composition length of the projective eigenvariety as a module. We give some upper bounds for the two parameters, and characterize the case that there is only one eigenvector of the tensor corresponding to the spectral radius, i.e. the Perron vector. By applying the above results to the adjacency tensor of a connected uniform hypergraph, we give some upper bounds for the two parameters in terms of the structural parameters of the hypergraph such as path cover number, matching number and the maximum length of paths. [ABSTRACT FROM AUTHOR]

Let G be a graph and let A ( G ) be adjacency matrix of G . The positive inertia index (respectively, the negative inertia index) of G , denoted by p ( G ) (respectively, n ( G ) ), is defined to be the number of positive eigenvalues (respectively, negative eigenvalues) of A ( G ) . In this paper, we present the bounds for p ( G ) and n ( G ) as follows: m ( G ) − c ( G ) ≤ p ( G ) ≤ m ( G ) + c ( G ) , m ( G ) − c ( G ) ≤ n ( G ) ≤ m ( G ) + c ( G ) , where m ( G ) and c ( G ) are respectively the matching number and the cyclomatic number of G . Furthermore, we characterize the graphs which attain the upper bounds and the lower bounds respectively. [ABSTRACT FROM AUTHOR]

Let G be a simple graph or hypergraph, and let A ( G ) , L ( G ) , Q ( G ) be the adjacency, Laplacian and signless Laplacian tensors of G respectively. The largest H -eigenvalues (respectively, the spectral radii) of L ( G ) , Q ( G ) are denoted respectively by λ max L ( G ) , λ max Q ( G ) (respectively, ρ L ( G ) , ρ Q ( G ) ). It is known that for a connected non-bipartite simple graph G , λ max L ( G ) = ρ L ( G ) < ρ Q ( G ) . But this does not hold for non-odd-bipartite hypergraphs. We will investigate this problem by considering a class of generalized power hypergraphs G k , k 2 , which are constructed from simple connected graphs G by blowing up each vertex of G into a k 2 -set and preserving the adjacency of vertices. Suppose that G is non-bipartite, or equivalently G k , k 2 is non-odd-bipartite. We get the following spectral properties: (1) ρ L ( G k , k 2 ) = ρ Q ( G k , k 2 ) if and only if k is a multiple of 4; in this case λ max L ( G k , k 2 ) < ρ L ( G k , k 2 ) . (2) If k ≡ 2 ( mod 4 ) , then for sufficiently large k , λ max L ( G k , k 2 ) < ρ L ( G k , k 2 ) . Motivated by the study of hypergraphs G k , k 2 , for a connected non-odd-bipartite hypergraph G , we give a characterization of L ( G ) and Q ( G ) having the same spectra or the spectrum of A ( G ) being symmetric with respect to the origin, that is, L ( G ) and Q ( G ) , or A ( G ) and − A ( G ) are similar via a complex (necessarily non-real) diagonal matrix with modular-1 diagonal entries. So we give an answer to a question raised by Shao et al., that is, for a non-odd-bipartite hypergraph G , that L ( G ) and Q ( G ) have the same spectra can not imply they have the same H -spectra. [ABSTRACT FROM AUTHOR]

Let $$\fancyscript{B}(n,r)$$ be the set of all bicyclic graphs with $$n$$ vertices and $$r$$ cut edges. In this paper we determine the unique graph with maximal adjacency spectral radius or signless Laplacian spectral radius among all graphs in $$\fancyscript{B}(n,r)$$ . [ABSTRACT FROM AUTHOR]

A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and contains exactly one cycle (namely the class Ucn of graphs whose complements are unicyclic), and characterize the unique minimizing graph in Ucn when n ≥ 20. [ABSTRACT FROM AUTHOR]

Abstract: Let G be a graph and let be the adjacency matrix of G. The signature of G is the difference between the positive inertia index and the negative inertia index of . Ma et al. (2013) [10] conjectured that , where and respectively denote the number of cycles in G which have length and for some integers , and proved the conjecture holds for trees, unicyclic or bicyclic graphs. It is known that if G is bipartite, and the signature is closely related to the odd cycles or nonbipartiteness of a graph from the existing results. In this paper we show that the conjecture holds for line graphs and power trees. [Copyright &y& Elsevier]

Letbe a signed graph and letbe the adjacency matrix of. The nullity ofis the multiplicity of eigenvalue zero in the spectrum of. In this paper, we characterize the signed graphs of orderwith nullityor, and introduce a graph transformation which preserves the nullity. As an application we determine the unbalanced bicyclic signed graphs of orderwith nullityor, and signed bicyclic graphs (including simple bicyclic graphs) of orderwith nullity. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we determine the graph whose least eigenvalue of the signless Laplacian attains the minimum or maximum among all connected non-bipartite graphs of fixed order and given number of pendant vertices. Thus we obtain a lower bound and an upper bound for the least eigenvalue of the signless Laplacian of a graph in terms of the number of pendant vertices. [Copyright &y& Elsevier]

Abstract: In this paper we introduce the nullity of signed graphs, and give some results on the nullity of signed graphs with pendant trees. We characterize the unicyclic signed graphs of order n with nullity respectively. [Copyright &y& Elsevier]

Abstract: A connected graph with a unique cycle is called a unicyclic graph. A unicyclic graph with depth one may be thought of as being obtained from a cycle by appending pendent edges on each vertex in the cycle (for some integer ), denoted by . In this paper, we give a complete characterization on the nullity of the line graph as follows: Let . Then [(i)] if and only if and . [(ii)] if and only if and either [(1)] for , the length of any zero chain of is even and ; or [(2)] and one of and must hold. [(iii)] , otherwise. [Copyright &y& Elsevier]

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut edges. [ABSTRACT FROM AUTHOR]

Abstract: Let G be a simple graph, and let the least eigenvalue of the signless Laplacian of the graph G. In this paper we focus on the relations between the least eigenvalue and some parameters reflecting the graph bipartiteness. We introduce two parameters: the vertex bipartiteness and the edge bipartiteness , and show thatWe also define another parameter involved with a cut set, and prove thatwhere is the maximum degree of the graph G. The above two inequalities are very similar in form to those given by Fiedler and Mohar, respectively, with respect to the algebraic connectivity of Laplacian of graphs, which is used to characterize the connectedness of graphs. [Copyright &y& Elsevier]

Abstract: We investigate how the least eigenvalue of the signless Laplacian of a graph changes by relocating a bipartite branch from one vertex to another vertex, and minimize the least eigenvalue of the signless Laplacian among the class of connected graphs with fixed order which contains a given non-bipartite graph as an induced subgraph. [Copyright &y& Elsevier]

Abstract: Let be the set of the complements of trees of order n. In this paper, we characterize the unique graph whose least eigenvalue attains the minimum among all graphs in . [Copyright &y& Elsevier]

Abstract: The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we characterize the graphs with maximum signless Laplacian or adjacency spectral radius among all graphs with fixed order and given vertex or edge connectivity. We also discuss the minimum signless Laplacian or adjacency spectral radius of graphs subject to fixed connectivity. Consequently we give an upper bound of signless Laplacian or adjacency spectral radius of graphs in terms of connectivity. In addition we confirm a conjecture of Aouchiche and Hansen involving adjacency spectral radius and connectivity. [Copyright &y& Elsevier]

Abstract: In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all graphs of a fixed order and a given vertex (edge) independence number or vertex (edge) cover number, and get some bounds for the vertex (edge) independence number, vertex (edge) cover number of a graph in terms of the least eigenvalue of the graph. [Copyright &y& Elsevier]

Abstract: In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut vertices, and then obtain a lower bound for the least eigenvalue of a connected graph in terms of the number of cut vertices. During the discussion we also get some results for the spectral radius of a connected bipartite graph and its upper bound. [Copyright &y& Elsevier]

Abstract: The nullity of a graph is defined to be the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. In this paper, we obtain the nullity set of bipartite graphs of order , and characterize the bipartite graphs with nullity and the regular bipartite graphs with nullity . [Copyright &y& Elsevier]

Abstract: Let be a mixed graph and let be the Laplacian matrix of the graph . The first eigenvalue and the first eigenvectors of are respectively referred to the least nonzero eigenvalue and the corresponding eigenvectors of . In this paper we focus on the properties of the first eigenvalue and the first eigenvectors of a nonsingular unicyclic mixed graph (abbreviated to a NUM graph). We introduce the notion of characteristic set associated with the first eigenvectors, and then obtain some results on the sign structure of the first eigenvectors. By these results we determine the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order and fixed girth, and the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order. [Copyright &y& Elsevier]

Abstract: Let be a simple graph and be the adjacency matrix of . The eigenvalues of are those of . In this paper, we characterize the graphs with the minimal least eigenvalue among all graphs of fixed order with given vertex connectivity or edge connectivity. [Copyright &y& Elsevier]

Abstract: A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph is threshold (maximal) if and only if for every pair of vertices of , the sets , where denotes the neighbor set of in , are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed. [Copyright &y& Elsevier]

Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph. [ABSTRACT FROM AUTHOR]

Abstract: The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. In a recent work the trees with maximal Laplacian spread and with minimal Laplacian spread among all trees of fixed order are separately determined. In this work, we characterize the unique unicyclic graph with maximal Laplacian spread among all connected unicyclic graphs of fixed order. [Copyright &y& Elsevier]

Abstract: In this paper we introduce a new parameter for a graph called the minimum universal rank. This parameter is similar to the minimum rank of a graph. For a graph G the minimum universal rank of G is the minimum rank over all matrices of the form where A is the adjacency matrix of G, J is the all ones matrix and D is the matrix with the degrees of the vertices in the main diagonal, and are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of A. The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. [Copyright &y& Elsevier]

Abstract: A sufficient condition of adaptive synchronization in dynamical networks with coupling delays is gained, where the coupling configuration corresponds to a weighted graph. One can reduce edges to original graph such that the network more quickly achieves synchronization. Numerical simulations are given to illustrate the efficiency of theoretical results. [Copyright &y& Elsevier]