Common consequents in directed graphs
Comparison of Metric Spectral Gaps
Let A = (aij) ∊ Mn(ℝ) be an n by n symmetric stochastic matrix. For p ∊ [1, ∞) and a metric space (X, dX), let γ(A, dpx) be the infimum over those γ ∊ (0,∞] for which every x1, . . . , xn ∊ X satisfy [...] Thus γ (A, dpx) measures the magnitude of the nonlinear spectral gap of the matrix A with respect to the kernel dpX : X × X →[0,∞). We study pairs of metric spaces (X, dX) and (Y, dY ) for which there exists Ψ: (0,∞)→(0,∞) such that γ (A, dpX) ≤Ψ (A, dpY ) for every symmetric stochastic A ∊ Mn(ℝ)...
Complementary Pairs of Graphs With the Second Largest Eigenvalue not Exceeding (sqrt(5)-1)/2
Conditions for a totally positive completion in the case of a symmetrically placed cycle.
Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs
The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity. We present some new results describing the connections between the spectrum of a regular graph and other combinatorial parameters such as its generalized connectivity, toughness, and the existence of spanning trees with bounded degree.
Constante de Cheeger et première valeur propre non nulle du Laplacien d’un graphe de petite dimension
Constructing cospectral graphs.
Constructing fifteen infinite classes of nonregular bipartite integral graphs.
Constructions for type I trees with nonisomorphic Perron branches
A tree is classified as being type I provided that there are two or more Perron branches at its characteristic vertex. The question arises as to how one might construct such a tree in which the Perron branches at the characteristic vertex are not isomorphic. Motivated by an example of Grone and Merris, we produce a large class of such trees, and show how to construct others from them. We also investigate some of the properties of a subclass of these trees. Throughout, we exploit connections between...
Controllable graphs
Cospectral graphs on 12 vertices.
Cospectral Graphs With Least Eigenvalue at Least -2
Cover matrices of posets and their spectra
We analyze the spectra of the cover matrix of a given poset. Some consequences on the multiplicities are provided.
Coverings, heat kernels and spanning trees.
Coverings, Laplacians, and heat kernels of directed graphs.
Cut-off for large sums of graphs
If is the combinatorial Laplacian of a graph, converges to a matrix with identical coefficients. The speed of convergence is measured by the maximal entropy distance. When the graph is the sum of a large number of components, a cut-off phenomenon may occur: before some instant the distance to equilibrium tends to infinity; after that instant it tends to . A sufficient condition for cut-off is given, and the cut-off instant is expressed as a function of the gap and eigenvectors of components....
Cutpoints, lobes and the spectra of graphs