On the number of Laplacian eigenvalues of trees less than the average degree

Laplacian eigenvalues of trees have been studied by many researchers. They are closely related to the diameter, domination number, matching number and Laplacian energy of trees. The goal of this paper is to prove a conjecture on the number of Laplacian eigenvalues of trees that are less than the average degree.     

The eigenvalues of the Laplacian on locally finite networks

We consider the continuous Laplacian on an infinite locally finite network with equal edge lengths under natural transition conditions as continuity at the ramification nodes and classical Kirchhoff conditions at all vertices. It is shown that eigenvalues of the Laplacian in a L^∞-setting are closely related to those of the adjacency and transition operator of the network. In this way the point spectrum is determined completely in terms of combinatorial quantities and properties of the underlying graph as in the finite case [2]. Moreover, the occurrence of infinite geometric multiplicity on trees and some periodic graphs is investigated.     

Trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues

The signless Laplacian matrix of a graph G is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called Q-eigenvalues of G. A Q-eigenvalue of a graph G is called a Q-main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. In this work, all trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues are determined.     

The Estrada index of trees

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of its adjacency matrix. We determine the unique tree with maximum Estrada index among the set of trees with given number of pendant vertices. As applications, we determine trees with maximum Estrada index among the set of trees with given matching number, independence number, and domination number, respectively. Finally, we give a proof of a conjecture in [J. Li, X. Li, L. Wang, The minimal Estrada index of trees with two maximum degree vertices, MATCH Commun. Math. Comput. Chem. 64 (2010) 799-810] on trees with minimum Estrada index among the set of trees with two adjacent vertices of maximum degree.     

Integral trees of odd diameters

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. Recently, Csikvári proved the existence of integral trees of any even diameter. In the odd case, integral trees have been constructed with diameter at most 7. In this article, we show that for every odd integer n>1, there are infinitely many integral trees of diameter n. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Minimal Networks on the Regular n-Dimensional Simplex

The paper gives the proof of the following fact: all simple, i.e., having no nodes of degree 2, trees that span the vertices of the regular n-dimensional simplex can be realized as nondegenerate minimal parametric networks.     

The maximum multiplicity of the largest k-th eigenvalue in a matrix whose graph is acyclic or unicyclic

Given a graph $G$ we are interested in studying the symmetric matrices associated to $G$ with a fixed number of negative eigenvalues. For this class of matrices we focus on the maximum possible nullity. For trees this parameter has already been studied and plenty of applications are known. In this work we derive a formula for the maximum nullity and completely describe its behavior as a function of the number of negative eigenvalues. In addition, we also carefully describe the matrices associated with trees that attain this maximum nullity. The analysis is then extended to the more general class of unicyclic graphs. Further our work is applied to re-describing all possible partial inertias associated with trees, and is employed to study an instance of the inverse eigenvalue problem for certain trees.     

Spectra of Large Random Trees

We analyze the eigenvalues of the adjacency matrices of a wide variety of random trees. Using general, broadly applicable arguments based on the interlacing inequalities for the eigenvalues of a principal submatrix of a Hermitian matrix and a suitable notion of local weak convergence for an ensemble of random trees that we call probability fringe convergence, we show that the empirical spectral distributions for many random tree models converge to a deterministic (model-dependent) limit as the number of vertices goes to infinity. Moreover, the masses assigned by the empirical spectral distributions to individual points also converge in distribution to constants. We conclude for ensembles such as the linear preferential attachment models, random recursive trees, and the uniform random trees that the limiting spectral distribution has a set of atoms that is dense in the real line. We obtain lower bounds on the mass assigned to zero by the empirical spectral measures via the connection between the number of zero eigenvalues of the adjacency matrix of a tree and the cardinality of a maximal matching on the tree. In particular, we employ a simplified version of an algorithm due to Karp and Sipser to construct maximal matchings and understand their properties. Moreover, we show that the total weight of a weighted matching is asymptotically equivalent to a constant multiple of the number of vertices when the edge weights are independent, identically distributed, nonnegative random variables with finite expected value, thereby significantly extending a result obtained by Aldous and Steele in the special case of uniform random trees. We greatly generalize a celebrated result obtained by Schwenk for the uniform random trees by showing that if any ensemble converges in the probability fringe sense and a very mild further condition holds, then, with probability converging to one, the spectrum of a realization is shared by at least one other (nonisomorphic) tree. For the linear preferential attachment model with parameter a>?1, we show that for any fixed k, the k largest eigenvalues jointly converge in distribution to a nontrivial limit when rescaled by $n^{1/2\gamma_{a}}$ , where ?? _a =a+2 is the Malthusian rate of growth parameter for an associated continuous-time branching process.     

Line graph of combinations of generalized Bethe trees: Eigenvalues and energy

We characterize the eigenvalues and energy of the line graph L(G) whenever G is (i) a generalized Bethe tree, (ii) a Bethe tree, (iii) a tree defined by generalized Bethe trees attached to a path, (iv) a tree defined by generalized Bethe trees having a common root, (v) a graph defined by copies of a generalized Bethe tree attached to a cycle and (vi) a graph defined by copies of a star attached to a cycle; in this case, explicit formulas for the eigenvalues and energy of L(G) are derived.     

Some Remarks on the Eigenvalue Multiplicities of the Laplacian on Infinite Locally Finite Trees

We consider the continuous Laplacian on an infinite uniformly locally finite network under natural transition conditions as continuity at the ramification nodes and the classical Kirchhoff flow condition at all vertices in a L ^∞-setting. The characterization of eigenvalues of infinite multiplicity for trees with finitely many boundary vertices (von Below and Lubary, Results Math 47:199–225, 2005, 8.6) is generalized to the case of infinitely many boundary vertices. Moreover, it is shown that on a tree, any eigenspace of infinite dimension contains a subspace isomorphic to ${\ell^\infty({\mathbb N})}$ . As for the zero eigenvalue, it is shown that a locally finite tree either is a Liouville space or has infinitely many linearly independent bounded harmonic functions if the edge lengths do not shrink to zero anywhere. This alternative is shown to be false on graphs containing circuits.     

On the spectra of certain rooted trees

Let T be an unweighted tree with vertex root v which is the union of two trees T₁=(V₁,E₁), T₂=(V₂,E₂) such that V₁ ∩ V₂ = {v} and T₁ and T₂ have the property that the vertices in each of their levels have equal degree. We characterize completely the eigenvalues of the adjacency matrix and of the Laplacian matrix of T. They are the eigenvalues of symmetric tridiagonal matrices whose entries are given in terms of the vertex degrees. Moreover, we give some results about the multiplicity of the eigenvalues. Applications to some particular trees are developed.     

Branch duplication for the construction of multiple eigenvalues in an Hermitian matrix whose graph is a tree

Suppose that the eigenvalues of an Hermitian matrix A whose graph is a tree T are known, as well as the eigenvalues of the principal submatrix of A corresponding to a certain branch of T. A method for constructing a larger tree T?', in which the branch is ‘`duplicated’', and an Hermitian matrix A′ whose graph is T?' is described. The eigenvalues of A' are all of those of A, together with those corresponding to the branch, including multiplicities. This idea is applied (1) to give a solution to the inverse eigenvalue problem for stars, (2) to prove that the known diameter lower bound, for the minimum number of distinct eigenvalues among Hermitian matrices with a given graph, is best possible for trees of bounded diameter, and (3) to increase the list of trees for which all possible lists for the possible spectra are know. A generalization of the basic branch duplication method is presented.     

Trees with very few eigenvalues

The number of distinct eigenvalues of the adjacency matrix of a graph is bounded below by the diameter of the graph plus one. Many graphs that achieve this lower bound exhibit much symmetry, for example, distance-transitive and distance-regular graphs. Here we provide a recursive construction that will create graphs having the fewest possible eigenvalues. This construction is best at creating trees, but will also create cyclic graphs meeting the lower bound. Unlike the graphs mentioned above, many of the graphs constructed do not exhibit large amounts of symmetry. A corollary allows us to determine the values and multiplicities of all the nonsimple eigenvalues of the constructed graph.     

Integral trees of arbitrarily large diameters

In this paper, we construct trees having only integer eigenvalues with arbitrarily large diameters. In fact, we prove that for every finite set S of positive integers there exists a tree whose positive eigenvalues are exactly the elements of S. If the set S is different from the set {1} then the constructed tree will have diameter 2|S|.     

The inverse eigenvalue problem for linear trees

We prove the sufficiency of the Linear Superposition Principle for linear trees, which characterizes the spectra achievable by a real symmetric matrix whose underlying graph is a linear tree. The necessity was previously proven in [10]. This is the most general class of trees for which the inverse eigenvalue problem has been solved. We explore many consequences, including the Degree Conjecture for possible spectra, upper bounds for the minimum number of eigenvalues of multiplicity 1, and the equality of the diameter of a linear tree and its minimum number of distinct eigenvalues.     

Eigenvalues of graphs with vertices of large degree at distance three apart

We investigate the family of graphs with many large eigenvalues. It is not hard to see that every graph with many vertices of large degree that are pairwise at distance at least four from each other, has many large eigenvalues. We show that this does not hold if the vertices of large degree are at mutual distance three from each other. We explore this class of graphs further and provide some bounds on their eigenvalues.     

A matricial computation of rational quadrature formulas on the unit circle

A matricial computation of quadrature formulas for orthogonal rational functions on the unit circle, is presented in this paper. The nodes of these quadrature formulas are the zeros of the para-orthogonal rational functions with poles in the exterior of the unit circle and the weights are given by the corresponding Christoffel numbers. We show how these nodes can be obtained as the eigenvalues of the operator Möbius transformations of Hessenberg matrices and also as the eigenvalues of the operator Möbius transformations of five-diagonal matrices, recently obtained. We illustrate the preceding results with some numerical examples.     

On graphs with given main eigenvalues

An eigenvalue of a graph is main if it has an eigenvector, the sum of whose entries is not equal to zero. Extending previous results of Hagos and Hou et al. we obtain two conditions for graphs with given main eigenvalues. All trees and connected unicyclic graphs with exactly two main eigenvalues were characterized by Hou et al. Extending their results, we determine all bicyclic connected graphs with exactly two main eigenvalues.     

Mathematical aspects of ‘t Hooft’s eigenvalue problem in two-dimensional quantum chromodynamics

We consider the eigenvalue problem of t′ Hooft for the meson spectrum in 2-dimensional QCD. Various alternative formulations are discussed, and their equivalence is proved. Then, a variational characterization of the eigenfunctions and the eigenvalues is derived yielding that the spectrum is discrete and consists of denumerably many positive eigenvalues tending to infinity. The corresponding eigenfunctions are real analytic, and form a complete system in L₂ Finally, the number of nodes of each eigenfunctions is estimated.     

Limit laws for embedded trees: Applications to the integrated superBrownian excursion

We study three families of labeled plane trees. In all these trees, the root is labeled 0 and the labels of two adjacent nodes differ by 0,1, or ?1. One part of the paper is devoted to enumerative results. For each family, and for all j ∈ ?, we obtain closed form expressions for the following three generating functions: the generating function of trees having no label larger than j; the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled j; and finally the (bivariate) generating function of trees, counted by the number of edges and the number of nodes labeled at least, j. Strangely enough, all these series turn out to be algebraic, but we have no combinatorial intuition for this algebraicity. The other part of the paper is devoted to deriving limit laws from these enumerative results. In each of our families of trees, we endow the trees of size n with the uniform distribution and study the following random variables: M_n, the largest label occurring in a (random) tree; X_n(j), the number of nodes labeled j; and X(j), the number of nodes labeled j or more. We obtain limit laws for scaled versions of these random variables. Finally, we translate the above limit results into statements dealing with the integrated superBrownian excursion. In particular, we describe the law of the supremum of its support (thus recovering some earlier results obtained by Delmas) and the law of its distribution function at a given point. We also conjecture the law of its density (at a given point). © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006