Search

We investigate how the algebraic connectivity of a graph changes by relocating a connected branch from one vertex to another vertex, and then minimize the algebraic connectivity among all connected graphs of order n with fixed domination number γ≤n+23, and finally present a lower bound for the algebraic connectivity in terms of the domination number. We also characterize the minimum algebraic connectivity of graphs with domination number half their order. [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: 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: 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: 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]

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]