Search

In this paper, we investigate the traces of the adjacency tensor of uniform hypergraphs (simply called the traces of hypergraphs). We give new expressions for the traces of hypertrees and linear unicyclic hypergraphs by the weight function assigned to their connected sub-hypergraphs, and present some perturbation results for the traces of a hypergraph when its structure is locally changed. As an application we determine the unique hypertree with maximum Estrada index among all hypertrees with perfect matchings and given number of edges, and the unique unicyclic hypergraph with maximum Estrada index among all unicyclic hypergraph with girth 3 and given number of edges. [ABSTRACT FROM AUTHOR]

A hypergraph is said to be oriented if each edge-vertex incidence has a label of +1 or −1. An oriented hypergraph is called incidence balanced if there exists a bipartition of the vertex set such that every edge intersects one part of the bipartition in positively incident vertices with the edge and the other part in negatively incident vertices with the edge. In this paper, we investigate the incidence balance of oriented hypergraphs and induced signed hypergraphs by means of the eigenvalues of associated matrices and tensors and provide a spectral method to characterize the incidence balanced oriented hypergraphs and their induced signed hypergraphs. [ABSTRACT FROM AUTHOR]

For a nonnegative weakly irreducible tensor, its spectral radius is an eigenvalue corresponding to a unique positive eigenvector up to a scalar, called Perron vector. But including the Perron vector, it may have more than one eigenvector corresponding to the spectral radius. The projective eigenvariety associated with the spectral radius is the set of the eigenvectors corresponding to the spectral radius considered in the complex projective space. We prove that the dimension of the above projective eigenvariety is zero, i.e. there are finitely many eigenvectors associated with the spectral radius up to a scalar. We characterize a nonnegative combinatorially symmetric tensor for which the dimension of projective eigenvariety associated with spectral radius is greater than zero. Finally we apply those results to the adjacency tensors of uniform hypergraphs. [ABSTRACT FROM AUTHOR]

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]

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]

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]

Let G be connected uniform hypergraph and let A (G) be the adjacency tensor of G. The stabilizing index of G is exactly the number of eigenvectors of A (G) associated with the spectral radius, and the cyclic index of G is exactly the number of eigenvalues of A (G) with modulus equal to the spectral radius. Let G 1 ⊙ G 2 and G 1 □ G 2 be the coalescence and Cartesian product of connected m -uniform hypergraphs G 1 and G 2 respectively. In this paper, we give explicit formulas for the stabilizing indices and cyclic indices of G 1 ⊙ G 2 and G 1 □ G 2 in terms of those of G 1 and G 2 or the invariant divisors of their incidence matrices over Z m , respectively. [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]

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 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: 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: The spread of a graph is defined to be the difference between the largest eigenvalue and the least eigenvalue of the adjacency matrix of the graph. Let denote the set of connected unicyclic graphs of order n and girth k, and let denote the set of connected unicyclic graphs of order n. In this paper, we determine the unique graph with minimum least eigenvalue (respectively, the unique graph with maximum spread) among all graphs in . We, finally, characterize the unique graph with minimum least eigenvalue (respectively, the unique graph with maximum spread) among all graphs in . [Copyright &y& Elsevier]

Abstract: Let be a nonsingular connected mixed graph. We determine the mixed graphs on at least seven vertices with exactly two Laplacian eigenvalues greater than 2. In addition, all mixed graphs with exactly one Laplacian eigenvalue greater than 2 are also characterized. [Copyright &y& Elsevier]

Abstract: Let T be a tree and L be its Laplacian matrix. With respect to a given vector Y which gives a valuation of vertices of T, a vertex u of T is called a characteristic vertex if Y[u]=0 and if there is a vertex w adjacent to u with Y[w]≠0; and an edge {u, w} of T is called a characteristic edge if Y[u]Y[w]<0. The characteristic set of T with respect to Y, denoted by , is defined as the collection of all characteristic vertices and characteristic edges of T. For the kth smallest eigenvalue λ k (k ⩾2) of T, if λk > λ k−1, the corresponding eigenvector Y of λ k is called a k-vector. A tree T is called k-simple if for all k-vectors Y. We show that k-simple trees exist and characterize them. We also show the characteristic sets determined by all the k-vectors is the same, which is consistent with the property of 2-simple tree (i.e., arbitrary tree). Finally, we give some properties of the eigenvalues and eigenvectors of a k-simple tree. [Copyright &y& Elsevier]

Abstract: Let G =(V, E) be a simple graph and {λ 1(G),…, λ n (G)} be its adjacency spectrum. It is easy to see that if an edge is added between two isolated vertices, then one zero eigenvalue increases by 1, and another zero eigenvalue decreases by 1. Let G + be a connected graph obtained from G by adding an edge e ∉ E(G). In this paper, it will be proved that the spectrum of G + is different from that of G only in two places with one eigenvalue increases by m and another eigenvalue decreases by m, where m >0 is a rational number, if and only if G is an empty graph with order 2. It will also be proved that one cannot construct a new adjacency integral connected graph with order n ⩾3 from a known one by adding an edge. [Copyright &y& Elsevier]

Using the result on Fiedler vectors of a simple graph, we obtain a property on the structure of the eigenvectors of a nonsingular unicyclic mixed graph corresponding to its least eigenvalue. With the property, we get some results on minimizing and maximizing the least eigenvalue over all nonsingular unicyclic mixed graphs on n vertices with fixed girth. In particular, the graphs which minimize and maximize, respectively, the least eigenvalue are given over all such graphs with girth 3. [ABSTRACT FROM AUTHOR]

In this paper, we characterize the mixed graphs with exactly one Laplacian eigenvalue moving up by an integer and other Laplacian eigenvalues remaining invariant when an edge is added. The results extend those of Fan [Linear and Multilinear Algebra 50 (2002) 133] for general graphs, and So [Linear and Multilinear Algebra 46 (1999) 193] for simple graphs. [Copyright &y& Elsevier]

Let G be a connected graph and let T be an acyclic set of edges of G. A partial orientation σ of G with respect to T is an orientation of the edges of G except those edges of T , the resulting graph associated with which is denoted by G T σ. In this paper we prove that there exists a partial orientation σ of G with respect to T such that the largest eigenvalue of the Hermitian adjacency matrix of G T σ is at most the largest absolute value of the roots of the matching polynomial of G. [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]