# Questions tagged [spectral-graph-theory]

Questions related to the spectrum of graphs, defined using one of the possible variants of the discrete Laplace operator or Laplacian matrix. See https://en.wikipedia.org/wiki/Discrete_Laplace_operator

282 questions
Filter by
Sorted by
Tagged with
59 views

251 views

### What's the full assumption for Laplacian matrix $L=BB^T=\Delta-A$?

Graph with no-selfloop, no-multi-edges, unweighted. directed For directed graph Adjacency matrix is a non-symmetric matrix $A_{in}$ considering indegree or $A_{out}$ considering outdegree. Degree ...
362 views

### Understanding Gillman's proof of the Chernoff bound for expander graphs

My question is about the proof of Claim 1 in this paper: Gillman (1993). At the end of the proof, the author says: The matrix product $U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$, ...
175 views

### Co-spectral fractional isomorphic graphs with different Laplacian spectrum

I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) such that $G$ and $H$ are cospectral (i.e., their adjacency matrices $A_G$ and $A_H$ ...
187 views

### Upper bounds for the second largest eigenvalue in terms of degree?

I am looking for upper bounds on the second largest eigenvalue, $\lambda_2(G)$ of a given graph $G$, with respect to minimum/maximum degrees of the graph. I looked around for some existing bounds most ...
219 views

### Graph Fourier transform definition

I have a question about the definition of the graph Fourier transform. Let me start with definition. Let $A$ be the adjacency matrix of a graph $G$ with vertex set $V = \{1, 2, \dots, n\}$. The ...
153 views

### Laplace spectra of “half” grid graph

Let $G=(E,V)$ be a simple graph. The graph Laplacian is given by $$L= D-A,$$ where $D$ is the degree matrix (diagonal matrix with entries corresponding to the degree of the vertex) and $A$ the ...
207 views

### Eigenvalues of the Laplacian of the directed De Bruijn graph

We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ ...
193 views

### Graph Laplacian Operator

Consider the linear operator $\mathbb{L} : L^2([0,1])\to L^2([0,1])$ defined by $$(\mathbb{L}f)(x) = \int_0^1 xy(f(x)-f(y)) \mathrm{d}y$$ for all $f\in L^2([0,1])$ and $x \in [0,1]$. Is $\mathbb{L}$...
139 views

### Are there graphs with irrational eigenvalues which are all $>1$?

The eigenvalues associated to a graph's adjacency matrix are necessarily algebraic integers, because the adjacency matrix itself is entirely integer. I'm curious as to whether it's possible to have ...