Search

The normalized distance Laplacian of a graph G is defined as D L (G) = T (G) − 1 / 2 (T (G) − D (G)) T (G) − 1 / 2 where D (G) is the matrix with pairwise distances between vertices and T (G) is the diagonal transmission matrix. In this project, we study the minimum and maximum spectral radii associated with this matrix, and the structures of the graphs that achieve these values. In particular, we prove a conjecture of Reinhart that the complete graph is the unique graph with minimum spectral radius, and we give several partial results towards a second conjecture of Reinhart regarding which graph has the maximum spectral radius. [ABSTRACT FROM AUTHOR]

The unique graphs with maximum spectral radius and signless Laplacian spectral radius are determined among trees, unicyclic graphs and bicyclic graphs respectively with fixed numbers of vertices and branch vertices (vertices of degree at least 3) using a unified approach. [ABSTRACT FROM AUTHOR]

By a unified approach, we present sufficient conditions based on spectral radius for a graph to be k -connected, k -edge-connected, k -Hamiltonian, k -edge-Hamiltonian, β -deficient and k -path-coverable. [ABSTRACT FROM AUTHOR]

Let ρ ( D ( G )) denote the distance spectral radius of a graph G and ∂ ( G → ) denote the distance signless Laplacian spectral radius of a digraph G → . Let G n , k D be the set of all k -connected graphs of order n with diameter D . In this paper, we first determine the unique graph with minimum distance spectral radius in G n , k D ; we then give sharp upper and lower bounds for the distance signless Laplacian spectral radius of strongly connected digraphs; we also characterize the digraphs having the maximal and minimal distance signless Laplacian spectral radii among all strongly connected digraphs; furthermore, we determine the extremal digraph with the minimal distance signless Laplacian spectral radius with given dichromatic number. [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 spectral radius of a graph is the largest eigenvalue of its adjacency matrix. P. Hansen and D. Stevanović (2008) [9] determined the graphs with maximum spectral radius among all connected graphs of order n with diameter D . In this paper, we generalize this result to k -connected graphs of order n with diameter D . [ABSTRACT FROM AUTHOR]

In the paper, we will determine the graphs with maximal spectral radius among all the trees with n vertices and independence number α for ⌈ n 2 ⌉ ≤ α ≤ n − 1 . [ABSTRACT FROM AUTHOR]

Let D be a strongly connected digraph and A(D) be the adjacency matrix of D. Let diag (D) be the diagonal matrix with outdegrees of the vertices of D and Q(D)=diag (D)+A(D) be the signless Laplacian matrix of D. The spectral radius of Q(D) is called the signless Laplacian spectral radius of D, denoted by q(D). In this paper, we give a sharp bound on q(D) where D has a given outdegree sequence and compare the bound with known bounds. We establish some sharp upper or lower bound on q(D) with some given parameter such as clique number, girth or vertex connectivity, and characterize the extremal graph. In addition, we also determine the unique digraph which achieves the minimum (or maximum), the second minimum (or maximum), the third minimum, the fourth minimum spectral radius and signless Laplacian spectral radius among all strongly connected digraphs, and answer the open problem proposed by Lin and Shu [14] [ABSTRACT FROM AUTHOR]

Let G=(V,E) be a simple connected weighted graph on n vertices, in which the edge weights are positive definite matrices. The eigenvalues of G are the eigenvalues of its adjacency matrix. In this note, we present a correction in equality part in Theorem 2 [S. Sorgun, S. Büyükköse, The new upper bounds on the spectral radius of weighted graphs, Appl. Math. Comput. 218 (2012) 5231–5238]. In addition, some related results are also provided. [ABSTRACT FROM AUTHOR]

Abstract: We show that the so-called diamond alternating sign matrix is the unique alternating sign matrix with maximum spectral radius , and that . [Copyright &y& Elsevier]

Abstract: Let G be a simple connected graph of order n with degree sequence in non-increasing order. The signless Laplacian spectral radius of G is the largest eigenvalue of its signless Laplacian matrix . In this paper, we give a sharp upper bound on the signless Laplacian spectral radius in terms of , which improves and generalizes some known results. [Copyright &y& Elsevier]

Abstract: The spectral radius of a graph G is the largest eigenvalue of its adjacency matrix. Woo and Neumaier discovered that a connected graph G with is either a dagger, an open quipu, or a closed quipu. The reverse statement is not true. Many open quipus and closed quipus have spectral radii greater than . In this paper we proved the following results. For any open quipu G on n vertices () with spectral radius less than , its diameter satisfies . This bound is tight. For any closed quipu G on n vertices () with spectral radius less than , its diameter satisfies . The upper bound is tight while the lower bound is asymptotically tight. Let be a graph with minimal spectral radius among all connected graphs on n vertices with diameter D. For and , we proved that is the unique graph obtained by attaching two paths of lengths and to a pair of antipodal vertices of the even cycle . This result is tight. Thus we settled a conjecture of Cioabaˇ–van Dam–Koolen–Lee, who previously proved a special case for and n large enough. [Copyright &y& Elsevier]

Abstract: Let be a simple connected graph. Denote by the diagonal matrix of its vertex degrees and by its adjacency matrix. Then the signless Laplacian matrix of G is . In this paper, we obtain some new and improved sharp upper bounds on the spectral radius of the signless Laplacian matrix of a graph G. [Copyright &y& Elsevier]

Abstract: Let G be a simple graph with vertices , of degrees , respectively. Let A be the -adjacency matrix of G and D be the diagonal matrix diag. is called the signless Laplacian of G. The largest eigenvalue of is called the signless Laplacian spectral radius or Q-spectral radius of G. Denote by the chromatic number for a graph G. In this paper, for graphs with order n, the extremal graphs with both the given chromatic number and the maximal Q-spectral radius are characterized, the extremal graphs with both the given chromatic number and the minimal Q-spectral radius are characterized as well. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices ( fixed), which achieves the maximal signless Laplacian spectral radius? We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at , where is a tree obtained from a star and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of and give some results. [Copyright &y& Elsevier]

Abstract: The independence number of is defined as the maximum cardinality of a set of pairwise non-adjacent vertices which is called an independent set. In this paper, we characterize the graphs which have the minimum spectral radius among all the connected graphs of order with independence number . [Copyright &y& Elsevier]

Abstract: A connected graph is called a quasi-k-cyclic graph, if there exists a vertex such that is a k-cyclic graph (connected with cyclomatic number k). In this paper we identify in the set of quasi-k-cyclic graphs (for ) those graphs whose spectral radius of the adjacency matrix (and the signless Laplacian if ) is the largest. In addition, for quasi-unicyclic graphs we identify as well those graphs whose spectral radius of the adjacency matrix is the second largest. [Copyright &y& Elsevier]

Abstract: A semiregular tree is a tree where all non-pendant vertices have the same degree. Among all semiregular trees with fixed order and degree, a graph with minimal (adjacency/Laplacian) spectral radius is a caterpillar. Counter examples show that the result cannot be generalized to the class of trees with a given (non-constant) degree sequence. [Copyright &y& Elsevier]

Abstract: Let be a graph with vertices and be the largest eigenvalue of the adjacency matrix of . We study how large can be when does not contain cycles and paths of specified order. In particular, we determine the maximum spectral radius of graphs without paths of given length, and give tight bounds on the spectral radius of graphs without given even cycles. We also raise a number of open problems. [Copyright &y& Elsevier]

Abstract: We consider the set of unicyclic graphs with prescribed degree sequence. In this set we determine the (unique) graph with the largest spectral radius (or index) with respect to the adjacency matrix. In addition, we give a conjecture about the (unique) graph with the largest index in the set of connected graphs with prescribed degree sequence. [Copyright &y& Elsevier]

Abstract: Wilf’s eigenvalue upper bound on the chromatic number is extended to the setting of digraphs. The proof uses a generalization of Brooks’ Theorem to digraph colorings. [Copyright &y& Elsevier]

Abstract: We study graphs with spectral radius at most and refine results by Woo and Neumaier [R. Woo, A. Neumaier, On graphs whose spectral radius is bounded by , Graphs Combinatorics 23 (2007) 713–726]. We study the limit points of the spectral radii of certain families of graphs, and apply the results to the problem of minimizing the spectral radius among the graphs with a given number of vertices and diameter. In particular, we consider the cases when the diameter is about half the number of vertices, and when the diameter is near the number of vertices. We prove certain instances of a conjecture posed by Van Dam and Kooij [E. R. Van Dam, R. E. Kooij, The minimal spectral radius of graphs with a given diameter, Linear Algebra Appl. 423 (2007) 408–419] and show that the conjecture is false for the other instances. [Copyright &y& Elsevier]

Abstract: Let A and B be nonsingular M-matrices. A lower bound on the minimum eigenvalue for the Hadamard product of and B, and a lower bound on the minimum eigenvalue for the Fan product of A and B are given. In addition, an upper bound on the spectral radius of nonnegative matrices A and B is also obtained. These bounds improve several existing results in some cases and the estimating formulas are easier to calculate for they are only depending on the entries of matrices A and B. [Copyright &y& Elsevier]

Abstract: If A and B are nonsingular M-matrices, a lower bound on the smallest eigenvalue for the Fan product of A and B is given. In addition, using the estimate on the perron root of nonnegative matrices, we also obtain an upper bound on the spectral radius for nonnegative matrices A and B. These bounds improve some existing results. [Copyright &y& Elsevier]

Abstract: The independence number of is defined as the maximum cardinality of a set of pairwise non-adjacent vertices which is called an independent set. In this paper, we characterize the graphs which have the minimum spectral radius among all the connected graphs of order with independence number . [Copyright &y& Elsevier]

Abstract: Let be the set of bicyclic graphs on vertices with girth . In this paper, we determine the unique graph with the maximal spectral radius among all graphs in . Moreover, the maximal spectral radius is a decreasing function on . [Copyright &y& Elsevier]