For any graph $G$, we associate a family of real symmetric matrices, $S(G)$, where for any $A \in S(G)$, the location of the nonzero off-diagonal entries of $A$ are governed by the adjacency structure of $G$. Let $q(G)$ represent the minimum number of distinct eigenvalues over all matrices in $S(G)$. In this work, we provide an alternative technique to establish that $q(G) \leq 4$ for any threshold graph $G$ as presented in [L. Emilio Allem, C. Hoppen, J. Lazzarin, L. Siviero Sibemberg, F. Colman Tura, The minimum number of distinct eigenvalues of a threshold graph is at most 4, Linear Algebra and its Applications, 726 (2025) 32 to 53]. In addition, we show that all connected threshold graphs admit a matrix having any four distinct eigenvalues. Further
Let $S_k(G)$ denote the sum of the $k$ largest eigenvalues of a graph $G$. Motivated by the classical Hoffman program for the spectral radius of a graph, we investigate an additive Hoffman-type problem for $S_k(G)$. For each fixed $k\geq 2$ and sufficiently large order $n$, we characterize all connected graphs satisfyi...
Shao-Wei Sun, Meng-Yao Guo, Hong-Yan Ge et al.· 0 citations
Let $G$ be a connected graph, and let $\lambda_1(G)>\lambda_2(G)$ denote its two largest adjacency eigenvalues. The spectral gap of $G$ is defined as the difference $\lambda_1(G) - \lambda_2(G)$. For integers $r\geq 2$ and $s\geq 0$, the double kite $DK(r,s)$ is formed by taking two vertex-disjoint copies of the comple...
For a graph $G$, let $s^+(G)$ and $s^-(G)$ denote the sums of the squares of its positive and negative adjacency eigenvalues. We determine all equality cases in the conjecture of Elphick, Farber, Goldberg, and Wocjan that every connected graph $G$ on $n$ vertices satisfies \[ \min \{s^+(G),s^-(G)\}\ge n-1. \] Namely, e...
A graph $G=(V,E)$ is called $d$-rigid if, for a generic embedding of its vertices in $\mathbb{R}^d$, the only continuous motions of the vertices preserving the distances between all pairs of adjacent vertices are those induced from the isometries of $\mathbb{R}^d$ (that is, translations and rotations of the whole graph...
Michael Krivelevich, Alan Lew, Peleg Michaeli· 0 citations
For a graph $G$ of order $n$, put $\sigma(G)=(\lambda_1(G)+\lambda_n(G))/n$. We determine the first three largest values of this invariant among nonbipartite distance-regular graphs of diameter three and odd girth at least seven. The unique maximizer is the folded $7$-cube, with value $1/32$; the unique second maximize...
Let $\Gamma^s(2,q)$ be the graph induced in the Grassmann graph by the $q$-ary simplex codes of dimension 2. For $q=4$, this graph is known to have diameter 3. We prove that the same diameter occurs for every prime power $q\geq5$. Together with the elementary cases $q=2,3$, this gives diam$\Gamma^s(2,q)=0,2,3$ for $q=2...
A. Siemaszko· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
