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]

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]

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