Minimum supports of eigenfunctions of graphs: a survey

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.

Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random.

Spectral graph theory is a captivating area of graph theory that employs the eigenvalues and eigenvectors of matrices associated with graphs to study them. In this paper, we present a collection of $20$ topics in spectral graph theory, covering a range of open problems and conjectures. Our focus is primarily on the adjacency matrix of graphs, and for each topic, we provide a brief historical overview.

The Laplacian matrix of a simple graph is the difference of the diagonal matrix of vertex degree and the (0,1) adjacency matrix. In the past decades, the Laplacian spectrum has received much more and more attention, since it has been applied to several fields, such as randomized algorithms, combinatorial optimization problems and machine learning. This paper is primarily a survey of various aspects of the eigenvalues of the Laplacian matrix of a graph for the past teens. In a...

The Star graph $S_n$, $n\ge 3$, is the Cayley graph on the symmetric group $Sym_n$ generated by the set of transpositions $\{(12),(13),\ldots,(1n)\}$. In this work we study eigenfunctions of $S_n$ corresponding to the second largest eigenvalue $n-2$. For $n\ge 8$ and $n=3$, we find the minimum cardinality of the support of an eigenfunction of $S_n$ corresponding to the second largest eigenvalue and obtain a characterization of eigenfunctions with the minimum cardinality of th...

We improve recent results relating graph eigenvalues to other graph parameters like girth, domination number, and minimum degree.

Complex networks or graphs are ubiquitous in sciences and engineering: biological networks, brain networks, transportation networks, social networks, and the World Wide Web, to name a few. Spectral graph theory provides a set of useful techniques and models for understanding `patterns of interconnectedness' in a graph. Our prime focus in this paper is on the following question: Is there a unified explanation and description of the fundamental spectral graph methods? There are...

Let $G$ be a graph, and let $\lambda(G)$ denote the smallest eigenvalue of $G$. First, we provide an upper bound for $\lambda(G)$ based on induced bipartite subgraphs of $G$. Consequently, we extract two other upper bounds, one relying on the average degrees of induced bipartite subgraphs and a more explicit one in terms of the chromatic number and the independence number of $G$. In particular, motivated by our bounds, we introduce two graph invariants that are of interest on...

We propose an approach to graph sparsification based on the idea of preserving the smallest $k$ eigenvalues and eigenvectors of the Graph Laplacian. This is motivated by the fact that small eigenvalues and their associated eigenvectors tend to be more informative of the global structure and geometry of the graph than larger eigenvalues and their eigenvectors. The set of all weighted subgraphs of a graph $G$ that have the same first $k$ eigenvalues (and eigenvectors) as $G$ is...

This article is concerned with properties of delocalization for eigenfunctions of Schr\"odinger operators on large finite graphs. More specifically, we show that the eigenfunctions have a large support and we assess their lp-norms. Our estimates hold for any fixed, possibly irregular graph, in prescribed energy regions, and also for certain sequences of graphs such as N-lifts.