On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Large families of laplacian isospectral graphs

Two graphs are isomorphic only if they are Laplacian isospectral, that is, their Laplacian matrices share the same multiset of eigenvalues. Large families of nonisomorphic Laplacian isospectral graphs are exhibited for which the common multiset of eigenvalues consists entirely of integers.     

Large families of laplacian isospectral graphs

Two graphs are isomorphic only if they are Laplacian isospectral, that is, their Laplacian matrices share the same multiset of eigenvalues. Large families of nonisomorphic Laplacian isospectral graphs are exhibited for which the common multiset of eigenvalues consists entirely of integers.     

Linear algorithms for testing the sign stability of a matrix and for findingZ-maximum matchings in acyclic graphs

Summary Ann×n real matrixA=(a _ij ) isstable if each eigenvalue has negative real part, andsign stable (orqualitatively stable) if each matrix B with the same sign-pattern asA is stable, regardless of the magnitudes ofB's entries. Sign stability is of special interest whenA is associated with certain models from ecology or economics in which the actual magnitudes of thea _ij may be very difficult to determine. Using a characterization due to Quirk and Ruppert, and to Jeffries, an efficient algorithm is developed for testing the sign stability ofA. Its time-and-space-complexity are both 0(n ²), and whenA is properly presented that is reduced to 0(max{n, number of nonzero entries ofA}). Part of the algorithm involves maximum matchings, and that subject is treated for its own sake in two final sections.     

Algebraic connectivity of directed graphs

We consider a generalization of Fiedler's notion of algebraic connectivity to directed graphs. We show that several properties of Fiedler's definition remain valid for directed graphs and present properties peculiar to directed graphs. We prove inequalities relating the algebraic connectivity to quantities such as the bisection width, maximum directed cut and the isoperimetric number. Finally, we illustrate an application to the synchronization in networks of coupled chaotic systems.     

Algebraic connectivity of directed graphs

We consider a generalization of Fiedler's notion of algebraic connectivity to directed graphs. We show that several properties of Fiedler's definition remain valid for directed graphs and present properties peculiar to directed graphs. We prove inequalities relating the algebraic connectivity to quantities such as the bisection width, maximum directed cut and the isoperimetric number. Finally, we illustrate an application to the synchronization in networks of coupled chaotic systems.     

Maximizing Algebraic Connectivity Over Unicyclic Graphs

We consider the class of unicyclic graphs on n vertices with girth g, and over that class, we attempt to determine which graph maximizes the algebraic connectivity. When g is fixed, we show that there is an N such that for each n>N, the maximizing graph consists of a g cycle with n?g pendant vertices adjacent to a common vertex on the cycle. We also provide a bound on N. On the other hand, when g is large relative to n, we show that this graph does not maximize the algebraic connectivity, and we give a partial discussion of the nature of the maximizing graph in that situation.     

A Class of M-matrices whose Graphs are Trees

In this article, we characterize generalized ultrametric matrices whose inverses are tree-diagonal. This generalizes the results of McDonald, Nabben, Neumann, Schneider and Tsatsomeros for tri-diagonal matrices.     

Sampling measures for Bergman spaces on the unit disk

We provide a characterization of the sampling measures for the Bergman spaces. These are the positive measures on the unit disk for which there exists a constant such that These are the continuous analogues of the sets of sampling characterized by K. Seip [13,14] and A. Schuster [12]. Our characterization is in terms of weak* limits of the Moebius transformations of the measure , and mimics the notion for sequences that sampling means being uniformly far from zero sets. Received: 26 October 1998 / in revised form: 25 Juni 1999     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

Corrigendum

In [] the authors constructed, for each r∈ (0,1), a function from a homogeneous tree of degree 2t to the open unit disk in the complex plane mapping the root of the tree to 0 and any pair of neighbors to points at hyperbolic distance r. Correspondingly, there is a free group of rank t of Möbius transformations such that the vertices of the tree are mapped to the orbit of 0, and the edges to geodesic arcs. One of the principal results of [] is to show that this function is an embedding of the tree when cos(π /2t)≤ r<1. This corrigendum fills a gap in the argument.     

Frobenius type theorems in the noncommutative case ∗

The classification of semilinear transformations preserving the determinant over a noncommutative local ring is given. For local Ore domains we obtain a classification of Adjamagbo determinant preservers. The developed technique allows us to classify Dieudonné determinant preservers for division rings which may be infinite dimensional over the center.