Search

We study limit points of the spectral radii of Laplacian matrices of graphs. We adapted the method used by J. B. Shearer in 1989, devised to prove the density of adjacency limit points of caterpillars, to Laplacian limit points. We show that this fails, in the sense that there is an interval for which the method produces no limit points. Then we generalize the method to Laplacian limit points of linear trees and prove that it generates a larger set of limit points. The results of this manuscript may provide important tools for proving the density of Laplacian limit points in $[4.38+, \infty)$.

We study limit points of the spectral radii of $A_{\alpha}$-matrices of graphs. Adapting a method used by J. B. Shearer in 1989, we prove a density property of $A_{\alpha}$-limit points of caterpillars for $\alpha$ close to zero. Precisely, we show that for $\alpha \in [0, 1/2)$ there exists a positive number $\tau_2(\alpha)>2$ such that any value $\lambda> \tau_2(\alpha)$ is an $A_{\alpha}$-limit point. We also determine the existence of other intervals for which all its points are $A_{\alpha}$-limit points., Comment: 22 pages

In this note, we present a structural description of certain connected cographs having $k \geq 2$ main signless Laplacian eigenvalues. This result allows us to characterize the cographs which are quasi-threshold graphs with two main $\mathbf{Q}$-eigenvalues. In addition, we describe all the quasi-threshold graphs belonging to the subclass of generalized core-satellite graphs with $k \geq 2$ main $\mathbf{Q}$-eigenvalues.

We show that for threshold graphs, the eigenvalues of the signless Laplacian matrix interlace with the degrees of the vertices. As an application, we show that the signless Brouwer conjecture holds for threshold graphs, i.e., for threshold graphs the sum of the k largest eigenvalues is bounded by the number of edges plus k + 1 choose 2., Comment: 14 pages, 3 figures

Given a tree $T$, let $q(T)$ be the minimum number of distinct eigenvalues in a symmetric matrix whose underlying graph is $T$. It is well known that $q(T)\geq d(T)+1$, where $d(T)$ is the diameter of $T$, and a tree $T$ is said to be diminimal if $q(T)=d(T)+1$. In this paper, we present families of diminimal trees of any fixed diameter. Our proof is constructive, allowing us to compute, for any diminimal tree $T$ of diameter $d$ in these families, a symmetric matrix $M$ with underlying graph $T$ whose spectrum has exactly $d+1$ distinct eigenvalues., Comment: 29 pages, 10 figures

Given a digraph D, the complementarity spectrum of the digraph is defined as the set of complementarity eigenvalues of its adjacency matrix. This complementarity spectrum has been shown to be useful in several fields, particularly in spectral graph theory. The differences between the properties of the complementarity spectrum for (undirected) graphs and for digraphs, makes the study of the latter of particular interest, and characterizing strongly connected digraphs with a small number of complementarity eigenvalues is a non trivial problem. Recently, strongly connected digraphs with one and two complementarity eigenvalues have been completely characterized. In this paper we study strongly connected digraphs with exactly three elements in the complementarity spectrum, ending with a complete characterization. This leads to a structural characterization of general digraphs having three complementarity eigenvalues., Comment: J Algebr Comb (2023)

In this paper we study the complementarity spectrum of digraphs, with special attention to the problem of digraph characterization through this complementarity spectrum. That is, whether two non-isomorphic digraphs with the same number of vertices can have the same complementarity eigenvalues. The complementarity eigenvalues of matrices, also called Pareto eigenvalues, has led to the study of the complementarity spectrum of (undirected) graphs and, in particular, the characterization of undirected graphs through these eigenvalues is an open problem. We characterize the digraphs with one and two complementarity eigenvalues, and we give examples of non-isomorphic digraphs with the same complementarity spectrum.

Let $M=(m_{ij})$ be a symmetric matrix of order $n$ whose elements lie in an arbitrary field $\mathbb{F}$, and let $G$ be the graph with vertex set $\{1,\ldots,n\}$ such that distinct vertices $i$ and $j$ are adjacent if and only if $m_{ij} \neq 0$. We introduce a dynamic programming algorithm that finds a diagonal matrix that is congruent to $M$. If $G$ is given with a tree decomposition $\mathcal{T}$ of width $k$, then this can be done in time $O(k|\mathcal{T}| + k^2 n)$, where $|\mathcal{T}|$ denotes the number of nodes in $\mathcal{T}$. Among other things, this allows one to compute the determinant, the rank and the inertia of a symmetric matrix in time $O(k|\mathcal{T}| + k^2 n)$.

In this paper, we define and obtain several properties of the (adjacency) energy of a hypergraph. In particular, bounds for this energy are obtained as functions of structural and spectral parameters, such as Zagreb index and spectral radius. We also study how the energy of a hypergraph varies when a vertex/edge is removed or when an edge is divied. In addition, we solved the extremal problem energy for the class of hyperstars, and show that the energy of a hypergraph is never an odd number.

We study a general class of recurrence relations that appear in the application of a matrix diagonalization procedure. We find general closed formula and determine analytical properties of the solutions. We finally apply these findings in several problems involving eigenvalues of graphs., Comment: 14 figures, 24 pages. Journal of Difference Equations and Applications

We address the problem of ordering trees with the same degree sequence by their spectral radii. To achieve that, we consider 2-switch transformations which preserve the degree sequence and establish when the index decreases. Our main contribution is to determine a total ordering of a particular family by their indices according to a given parameter related to sizes in the tree., Comment: 15 figures

In this paper, we study energies associated with hypergraphs. More precisely, we obtain results for the incidence and the singless Laplacian energies of uniform hypergraphs. In particular, we obtain bounds for the incidence energy as functions of well known parameters, such as maximum degree, Zagreb index and spectral radius. We also relate the incidence and signless Laplacian energies of a hypergraph with the adjacency energies of its subdivision graph and line multigraph, respectively. In addition, we compute the signless Laplacian energy for the class of the power hypergraphs., Comment: Keywords: Incidence Energy; Signless Laplacian Energy; Power Hypergraph

In this paper we obtain bounds for the extreme entries of the principal eigenvector of hypergraphs; these bounds are computed using the spectral radius and some classical parameters such as maximum and minimum degrees. We also study inequalities involving the ratio and difference between the two extreme entries of this vector., Comment: Keywords - Hypergraph; Adjacency tensor; Spectral radius; Principal eigenvector

In this paper we define signless Laplacian matrix of a hypergraph and obtain structural properties from its eigenvalues. We generalize several known results for graphs, relating the spectrum of this matrix with structural parameters of the hypergraph such as the maximum degree, diameter and the chromatic number. In addition, we characterize the complete signless Laplacian spectrum for the class of the power hypergraphs from the spectrum of its base hypergraph., Comment: Keywords - Spectral hypergraph theory; Signless Laplacian; Power hypergraph

A generalized power hypergraph $\mathcal{H}^k_s$ is obtained from a base hypergraph $\mathcal{H}$ by means of some simple edge-expansion operations. Kang, Liu, Qi and Yuan [8] proved that the nonzero eigenvalues of $\mathcal{H}$ give rise to nonzero eigenvalues of $\mathcal{H}^k_s$. In this paper we show that all nonzero eigenvalues of $\mathcal{H}^k_s$ may be computed from the eigenvalues of its base hypergraph $\mathcal{H}$ and of its subgraphs. To prove this, we derive spectral results about edge-expansion operations that may be interesting on their own sake., Comment: Keywords - Hypergraph; Generalized power hypergraph; Adjacency tensor; Spectral hypergraph

In this work we obtain basis for the null space of unicyclic graphs. We extend the null decomposition of trees from [11] for unicyclic graphs. As an application, we obtain closed formulas for the independence and matching numbers of unicyclic graphs just using the support of the graph., Comment: arXiv admin note: text overlap with arXiv:1907.07650

We characterize unicyclic graphs that are singular using the support of the null space of their pendant trees. From this, we obtain closed formulas for the independence and matching numbers of a unicyclic graph, based on the support of its subtrees. These formulas allows one to compute independence and matching numbers of unicyclic graphs using linear algebra methods.

We show that the number of Laplacian eigenvalues greater than the average degree of a tree having $n$ vertices is at most $\lfloor\frac{n}{2} \rfloor$., Comment: 31 pages, 27 figures, accepted for publication in JCTB

Finding a diagonal matrix congruent to $A - cI$ for constants $c$, where $A$ is the adjacency matrix of a graph $G$ allows us to quickly tell the number of eigenvalues in a given interval. If $G$ has clique-width $k$ and a corresponding $k$-expression is known, then diagonalization can be done in time $O(\text{poly}(k) n)$ where $n$ is the order of $G$., Comment: 25 pages

The parameter $\sigma(G)$ of a graph $G$ stands for the number of Laplacian eigenvalues greater than or equal to the average degree of $G$. In this work, we address the problem of characterizing those graphs $G$ having $\sigma(G)=1$. Our conjecture is that these graphs are stars plus a (possible empty) set of isolated vertices. We establish a link between $\sigma(G)$ and the number of anticomponents of $G$. As a by-product, we present some results which support the conjecture, by restricting our analysis to some classes of graphs., Comment: 10 pages

The index of a graph is the largest eigenvalue of its adjacency matrix. A starlike is a tree having a unique vertex of degree $r>2$. We show how to order the starlike trees with $n>3$ by their indices. In particular, the indices of starlike trees are all distinct.

Motivated by classic tree algorithms, in 1995 we designed a bottom-up $O(n)$ algorithm to compute the determinant of a tree's adjacency matrix $A$. In 2010 an $O(n)$ algorithm was found for constructing a diagonal matrix congruent to $A + xI_n$, $x \in \mathbb{R}$, enabling one to easily count the number of eigenvalues in any interval. A variation of the algorithm allows Laplacian eigenvalues in trees to be counted. We conjecture that for any tree $T$ of order $n \geq 2$, at least half of its Laplacian eigenvalues are less than $\bar{d} = 2 - \frac{2}{n}$, its average vertex degree.

Let $m_G(I)$ denote the number of Laplacian eigenvalues of a graph $G$ in an interval $I$, and let $\gamma(G)$ denote its domination number. We extend the recent result $m_G[0,1) \leq \gamma(G)$, and show that isolate-free graphs also satisfy $\gamma(G) \leq m_G[2,n]$. In pursuit of better understanding Laplacian eigenvalue distribution, we find applications for these inequalities. We relate these spectral parameters with the approximability of $\gamma(G)$, showing that $\frac{\gamma(G)}{m_G[0,1)} \not\in O(\log n)$. However, $\gamma(G) \leq m_G[2, n] \leq (c + 1) \gamma(G)$ for $c$-cyclic graphs, $c \geq 1$. For trees $T$, $\gamma(T) \leq m_T[2, n] \leq 2 \gamma(G)$.

We give an $O(n)$ time and space algorithm for constructing a diagonal matrix congruent to A+xI, where A is the adjacency matrix of a cograph and $x\in \mathbb{R}$. Applications include determining the number of eigenvalues of a cograph's adjacency matrix that lie in any interval, obtaining a formula for the inertia of a cograph, and exhibiting infinitely many pairs of equienergetic cographs with integer energy.

The Laplacian energy of a graph is the sum of the distances of the eigenvalues of the Laplacian matrix of the graph to the graph's average degree. The maximum Laplacian energy over all graphs on $n$ nodes and $m$ edges is conjectured to be attained for threshold graphs. We prove the conjecture to hold for graphs with the property that for each $k$ there is a threshold graph on the same number of nodes and edges whose sum of the $k$ largest Laplacian eigenvalues exceeds that of the $k$ largest Laplacian eigenvalues of the graph. We call such graphs spectrally threshold dominated. These graphs include split graphs and cographs and spectral threshold dominance is preserved by disjoint unions and taking complements. We conjecture that all graphs are spectrally threshold dominated. This conjecture turns out to be equivalent to Brouwer's conjecture concerning a bound on the sum of the $k$ largest Laplacian eigenvalues.

The resolvent energy of a graph $G$ of order $n$ is defined as $ER=\sum_{i=1}^n (n-\lambda_i)^{-1}$, where $\lambda_1,\lambda_2,\ldots,\lambda_n$ are the eigenvalues of $G$. In a recent work [Gutman et al., {\it MATCH Commun. Math. Comput. Chem.\/} {\bf 75} (2016) 279--290] the structure of the graphs extremal w.r.t. $ER$ were conjectured, based on an extensive computer--aided search. We now confirm the validity of some of these conjectures.