Search

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]

The spectral radius of a uniform hypergraph is defined to be that of the adjacency tensor of the hypergraph. It is known that the unique unicyclic hypergraph with the largest spectral radius is a nonlinear hypergraph, and the unique linear unicyclic hypergraph with the largest spectral radius is a power hypergraph. In this paper we determine the unique linear unicyclic hypergraph with the second or third largest spectral radius, where the former hypergraph is a power hypergraph and the latter hypergraph is a non-power hypergraph. [ABSTRACT FROM AUTHOR]

Let G be a connected m -uniform hypergraph. In this paper we mainly consider the eigenvectors of the Laplacian or signless Laplacian tensor of G associated with zero eigenvalue, called the first Laplacian or signless Laplacian eigenvectors of G. By means of the incidence matrix of G , the number of first Laplacian or signless Laplacian (or H-)eigenvectors can be obtained explicitly by solving the Smith normal form of the incidence matrix over Z m (or Z 2). Consequently, we prove that the number of first Laplacian (H-)eigenvectors is equal to the number of first signless Laplacian (H-)eigenvectors when zero is an (H-)eigenvalue of the signless Laplacian tensor. We establish a connection between first Laplacian (signless Laplacian) H-eigenvectors and the even (odd) bipartitions of G. [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]

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]

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 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: 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]

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 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]

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]

This paper presents a novel algorithm of stereo correspondence by using Laplacian spectra of graphs. Firstly, according to the feature points of two images to be matched, a Laplacian matrix with Gaussian-weighted distance is defined and a closed-form solution is given in terms of the matching matrix constructed on the vectors of eigenspace of the Laplacian matrix. Secondly, we introduce a new method to judge correspondences by using doubly stochastic matrix. Thirdly, in order to render our method robust, we describe an approach to embedding the Laplacian spectral method within the framework of iterative correspondence and transformation estimation. Experimental results show the feasibility and comparatively high accuracy of our methods. [Copyright &y& Elsevier]