Search

Let D (G) and D Q (G) = D i a g (T r) + D (G) be the distance matrix and distance signless Laplacian matrix of a simple strongly connected digraph G , respectively, where D i a g (T r) = diag (D 1 , D 2 , ... , D n) be the diagonal matrix with vertex transmissions of the digraph G. To track the gradual change of D (G) into D Q (G) , in this paper, we propose to study the convex combinations of D (G) and D i a g (T r) defined by D α (G) = α D i a g (T r) + (1 − α) D (G) , 0 ≤ α ≤ 1. This study reduces to merging the distance spectral and distance signless Laplacian spectral theories. The eigenvalue with the largest modulus of D α (G) is called the D α spectral radius of G , denoted by μ α (G). We determine the digraph which attains the maximum (or minimum) D α spectral radius among all strongly connected digraphs. Moreover, we also determine the digraphs which attain the minimum D α spectral radius among all strongly connected digraphs with given parameters such as dichromatic number, vertex connectivity or arc connectivity. [ABSTRACT FROM AUTHOR]

Let D ( G ) be the distance matrix of a connected graph G . The distance spectral radius of G , denoted by ∂ 1 ( G ) , is the largest eigenvalue of D ( G ) . In this paper we present a new transformation of a certain graph G that decreases ∂ 1 ( G ) . With the transformation, we partially confirm a conjecture proposed by Stevanović and Ilić [17] by showing that, if Δ ≥ ⌈ n 2 ⌉ , the double star S Δ , n − Δ uniquely minimizes the distance spectral radius among all trees on n vertices with maximum degree Δ . Moreover, the trees on n ≥ 10 vertices with the fourth and fifth least distance spectral radii are characterized. [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]

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: In this paper, we present preconditioned generalized accelerated overrelaxation methods. We compare the spectral radii of the iteration matrices of the preconditioned and original methods. The comparison results show that the preconditioned GAOR methods converge faster than the GAOR method whenever the GAOR method is convergent. Finally, we present two numerical examples to confirm our theoretical results. [Copyright &y& Elsevier]

Abstract: Let denote the distance matrix of a connected graph with order , where is equal to the distance between and in . The largest eigenvalue of is called the distance spectral radius of graph , denoted by . In this paper, some graft transformations that decrease or increase are given. With them, for the graphs with both order and pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when ; for , the extremal graphs with the maximum distance spectral radius are completely characterized. [Copyright &y& Elsevier]

Abstract: The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we provide structural and behavioral details of graphs with maximum Laplacian spectral radius among all bipartite connected graphs of given order and size. Using these results, we provide a unified approach to determine the graphs with maximum Laplacian spectral radii among all trees, and all bipartite unicyclic, bicyclic, tricyclic and quasi-tree graphs, respectively. [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 work, we introduce the class of -matrices for the max algebra and derive some properties of these that echo similar results for -matrices in the conventional algebra. In analogy with [1], we define the row--property and the S max -property of a finite set of nonnegative matrices. Moreover, we relate these concepts to stability questions for sets of matrices and difference inclusions in the max algebra. [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: 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: 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: In this primarily expository paper we survey classical and some more recent results on the spectra of digraphs, equivalently, the spectra of -matrices, with emphasis on the spectral radius. [Copyright &y& Elsevier]

Abstract: This paper deals with the joint spectral radius of a finite set of matrices. We say that a set of matrices has the finiteness property if the maximal rate of growth, in the multiplicative semigroup it generates, is given by the powers of a finite product. Here we address the problem of establishing the finiteness property of pairs of sign-matrices. Such problem is related to the conjecture that pairs of sign-matrices fulfil the finiteness property for any dimension. This would imply, by a recent result by Blondel and Jungers, that finite sets of rational matrices fulfil the finiteness property, which would be very important in terms of the computation of the joint spectral radius. The technique used in this paper could suggest an extension of the analysis to sign-matrices, which still remains an open problem. As a main tool of our proof we make use of a procedure to find a so-called real extremal polytope norm for the set. In particular, we present an algorithm which, under some suitable assumptions, is able to check if a certain product in the multiplicative semigroup is spectrum maximizing. For pairs of sign-matrices we develop the computations exactly and hence are able to prove analytically the finiteness property. On the other hand, the algorithm can be used in a floating point arithmetic and provide a general tool for approximating the joint spectral radius of a set of matrices. [Copyright &y& Elsevier]