Eigenvalues of neutral networks: interpolating between hypercubes

In this paper, we determine the set of all distinct eigenvalues of the line graph which is induced by the first and second layers of the hypercube $ Q_n $, $n>3$. We show that this graph has precisely five distinct eigenvalues and all of its eigenvalues are integers

In this work we present a survey of results on the problem of finding the minimum cardinality of the support of eigenfunctions of graphs.

We introduce and analyze a general model of a population evolving over a network of selectively neutral genotypes. We show that the population's limit distribution on the neutral network is solely determined by the network topology and given by the principal eigenvector of the network's adjacency matrix. Moreover, the average number of neutral mutant neighbors per individual is given by the matrix spectral radius. This quantifies the extent to which populations evolve mutatio...

In this paper extremal problems for uniform hypergraphs are studied in the general setting of hereditary properties. It turns out that extremal problems about edges are particular cases of a general analyic problem about a recently introduced graph parameter. The paper builds a basis for the systematic study of this parameter and illustrates a range of various proof tools. It is shown that extremal problems about the number of edges of uniform hypergraphs are asymptotically e...

We establish new bounds on the minimum number of distinct eigenvalues among real symmetric matrices with nonzero off-diagonal pattern described by the edges of a graph and apply these to determine the minimum number of distinct eigenvalues of several families of graphs and small graphs.

In this paper, we investigate the eigenvalues of the Laplacian matrix of the "graph of graphs", in which cubic graphs of order n are joined together using Whitehead moves. Our work follows recent results from arXiv:2303.13923 , which discovered a significant "bottleneck" in the graph of graphs. We found that their bottleneck implies an eigenvalue of order at most O(1). In fact, our main contribution is to expand upon this result by showing that the graph of graphs has increas...

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.

In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by...

A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that "any graph is close to being the disjoint union of expanders". Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. These results are obtained as corollaries of a new family of graphs, which we construct by pi...

The Hamming graph $H(n,q)$ is the graph whose vertices are the words of length $n$ over the alphabet $\{0,1,\ldots,q-1\}$, where two vertices are adjacent if they differ in exactly one coordinate. The adjacency matrix of $H(n,q)$ has $n+1$ distinct eigenvalues $n(q-1)-q\cdot i$ with corresponding eigenspaces $U_{i}(n,q)$ for $0\leq i\leq n$. In this work we study functions belonging to a direct sum $U_i(n,q)\oplus U_{i+1}(n,q)\oplus\ldots\oplus U_j(n,q)$ for $0\leq i\leq j\le...