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
43
questions
25
votes
3
answers
1k
views
Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?
30 years ago, Yves Colin de Verdière introduced the algebraic graph invariant $\mu(G)$ for any undirected graph $G$, see [1]. It was motivated by the study of the second eigenvalue of certain ...
61
votes
5
answers
11k
views
Intuitively, what does a graph Laplacian represent?
Recently I saw an MO post Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs? that got me interested. ...
39
votes
6
answers
4k
views
Is the Laplacian on a manifold the limit of graph Laplacians?
Here's the sort of thing I have in mind. Let $M$ be a Riemannian manifold, compact if it helps, and let $\Delta_M$ be the Laplace-Beltrami operator. Choose a sequence of triangulations of $M$ so ...
21
votes
5
answers
1k
views
Spectral theory of graph Laplacian besides $\lambda_2$
Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of ...
9
votes
3
answers
346
views
Spectrum of orthogonality graph (2)
The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent.
I am only interested when $4|n$, since otherwise $\Omega(n)$ is ...
7
votes
1
answer
944
views
Strategies for bounding the spectral norm of a tensor?
Let $A$ be a symmetric $k$-tensor over a real or complex vector field $W$. We may define its spectral norm $|A|$ by
$$|A| = \sup_{v\in W} \frac{|\langle A,x^{\otimes k}\rangle|}{|x|_2^k}.$$
(...
7
votes
2
answers
2k
views
Small eigenvalues and spectral clustering
Let $L$ be the discrete Laplacian associated to an undirected graph. It is well-known that the spectral gap of $L$, i.e. the smallest nonzero eigenvalue, is a measure of how well connected the graph ...
5
votes
1
answer
434
views
What is $e^{- \zeta_{\Delta} '(0)}$ for a $\Delta$ the Laplacian of a manifold?
For a connected, finite graph $G$, let $\lambda_1, \ldots, \lambda_n$ denote the nonzero eigenvalues of the graph Laplacian. We define $\zeta_G = \Sigma_{i = 1}^n \lambda_i^s$.
Then Kirkoffs Matrix-...
3
votes
1
answer
5k
views
Can the first non-zero eigenvalue of a Laplacian matrix with more than 1 zero valued eigenvalue be used to reorder an adjacency matrix?
I have a graph with multiple connected components, and its adjacency matrix. I form the Laplacian matrix (wiki Laplacian matrix), and from the 1K nodes there around ...
76
votes
4
answers
14k
views
What are good mathematical models for spider webs?
Sometimes I see spider webs in very complex surroundings, like in the middle of twigs in a tree or in a bush. I keep thinking “if you understand the spider web, you understand the space around it”. ...
18
votes
7
answers
3k
views
Spectral properties of Cayley graphs
Let $G$ be a finite group. Do eigenvalues of its Cayley graph say anything about the algebraic properties of $G$? The spectrum of Cayley graph may depend on the presentation, so it's not a good ...
17
votes
1
answer
592
views
Graph embeddings in the projective plane: for the 35 forbidden minors, do we know their Colin de Verdière numbers?
The Graph Minor Theorem of Robertson and Seymour asserts
that any minor-closed graph property is determined by a finite set
of forbidden graph minors. It is a broad generalization e.g. of the ...
12
votes
1
answer
829
views
How to find or constrain "particularly good" (two-sided) spectral expanders?
I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...
8
votes
3
answers
482
views
Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?
Ramanujan graphs are the best spectral expanders: $\lambda_2 \le 2\sqrt{d-1}$. I'm looking for some intuition for this value $2\sqrt{d-1}$.
Friedman showed that every random $d$-regular graph ...
8
votes
3
answers
7k
views
Spectrum of an adjacency matrix
The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real.
If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few ...
7
votes
3
answers
3k
views
Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian
The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)?
To make the question as self-contained as ...
7
votes
1
answer
336
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$ ...
7
votes
1
answer
912
views
Roots of matching polynomial of graph
At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...
6
votes
3
answers
429
views
Number of trees with the same matching number
Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.
I have been trying to compute the value of $\...
5
votes
1
answer
144
views
Inertia of a class of Cayley graphs
Let $H^n_2(d)$ be the Cayley graph with vertex set $\{0,1\}^n$ where two strings form an edge iff they have Hamming distance at least $d$. What is the inertia of these graphs, that is, the numbers of ...
5
votes
3
answers
387
views
Operation on Isospectral graphs
Suppose $G$ and $H$ are two isospectral connected graphs. Can we say anything about isospectrality of graphs that are obtained by applying a binary operation to $G$ and $H$?
For example, to take one ...
5
votes
1
answer
423
views
Second eigenvalue of suspension of a graph
Suppose I have some $d$-regular graph $G$. Let $\lambda = \max\{\lambda_2(G), |\lambda_n(G)|\}$ be the second largest eigenvalue of the adjacency matrix of $G$. Now take $\tilde{G}$, the suspension of ...
5
votes
2
answers
806
views
Database of adjacency matrices on cospectral non-isomorphic graph pairs
Is there a repository of cospectral non-isomorphic graphs available somewhere?
I am looking for list of $0/1$ adjacency matrix pairs that can be input data in tools such as MATLAB.
5
votes
0
answers
367
views
spectrum of orthogonality graphs
The orthogonality graph $\Omega(n)$ with $2^n$ vertices is the graph with vertex set $\{-1,+1\}^n$, with two vertices being adjacent if and only if they are orthogonal (as vectors in the standard ...
5
votes
2
answers
3k
views
Complex Eigenvalues of Directed Graphs
I have been computing eigenvalues of adjacency matrices for several directed (not necessarily strongly connected) graphs and one remarkable property seemed to hold (each graph that I have examined ...
5
votes
0
answers
258
views
(Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples
Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...
5
votes
1
answer
1k
views
How many distinct eigenvalues does a random graph have?
It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one.
But what is known about the ...
4
votes
1
answer
944
views
"Nice" eigenvectors for (square of) adjacency matrix of a bipartite graph?
Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix.
I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be ...
4
votes
1
answer
517
views
Closed paths, traces and spectra
Let $\Gamma$ be a graph. Write $A$ for its adjacency matrix. It is trivial to show that $\mathrm{Tr} A^k$ equals the number of closed walks of length k, that is, the number of $k$-step walks that ...
4
votes
0
answers
590
views
The Bilu-Linial conjecture and Ramanujan graphs
The Bilu-Linial conjecture claims that every $d-$regular graph has a $2-$lift such that for the signing matrix has its eigenvalues between $[-2\sqrt{d-1},2\sqrt{d-1}]$ (the ``signing matrix" is the ...
4
votes
1
answer
649
views
Embedding graphs into hyperbolic spaces
Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?)
I don't ...
4
votes
0
answers
236
views
Does the zeta regularized Laplacian determinant measure the volume of some parameter space? How many "spanning trees" on a manifold?
Let $(M,g)$ be a Riemannian manifold, with Laplacian $\Delta$. If $\lambda_i$ are the nonzero eigenvalues of $\Delta$, we can define the zeta function $\zeta(s) = \Sigma \lambda_i^{-s}$. By analytic ...
3
votes
1
answer
167
views
How to find non-isomorphic graphs with specific orders?
I work on a problem in my research. I have a graph, $G$, with $2n$ vertices. It has one connected component of order $2n-1$ and an isolated vertex. $\lambda_1\geq \lambda_2\geq \ldots \geq \lambda_{2n}...
3
votes
1
answer
656
views
Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?
Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$.
But do we have any quantitative ...
3
votes
1
answer
155
views
The spectral radius of a modified graph
Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$.
This situation has many different names: $G$ is called the cone or the ...
2
votes
0
answers
158
views
Closed geodesics and eigenvalues in a non-regular graph
Let $\Gamma$ be an undirected graph the degree of whose $n$ vertices is $\leq D$ without necessarily being constant. Say we have bounds of type $\leq \gamma^{2 k}$ for the number of closed geodesics ...
2
votes
0
answers
56
views
Antipodal vertices in spectral graph embeddings
Suppose your are given an antipodal graph $G=(V,E)$, that is, for every vertex $v\in V$ there is a unique maximally distant vertex $v'\in V$.
Under which condistions does the following hold:
If $\...
2
votes
1
answer
154
views
Gaussian bounds with exponential decay for discrete (graph) Dirichlet heat kernel
Let $\Omega$ be a finite, connected subset of $\mathbb{Z}^n$, $W_t$ a standard random walk on $\mathbb{Z}^n$ started at $x$, and $T_\Omega$ the first time at which $W_t$ leaves $\Omega$; consider
$$
P^...
2
votes
1
answer
124
views
Is the sum of the circulant matrix with a super upper triangular matrix diagonalizable?
By the circulant matrix $C$ in $M_n(\mathbb{R})$, we mean that
$$C=[e_n|e_1|\cdots|e_{n-1}]$$ where $e_1,\cdots,e_n$ are the standard basis vectors in $\mathbb{R}^n$. It is well-known that
$$C=\...
2
votes
3
answers
658
views
Non-isomorphic graphs with the same numbers of closed walks
Can somebody help me to construct two family of finite simple connected graph $G_i$ and $H_i$, $i=1, 2, \cdots,n$ ($n$ possibly large), such that:
$1)$ $G_i\ncong H_i$ for $i=1, 2, \cdots, n$
$2)$ $...
1
vote
0
answers
228
views
Lp norm estimates for the inverse of the Laplacian on a graph
I am looking at a finite connected graph and I would like to know what is the best [i.e. largest] constant $\lambda_p$ in
$$
\sum_x f(x) =0 \implies \| \Delta^{-1} f\|_{\ell^p} \leq \lambda_p^{-1} \|...
1
vote
2
answers
523
views
Is this general form of Lovasz theta function of circulant graphs?
Let $G$ be a cirulant graph with no loops at vertices and vertex degree $d$. Is the Lovasz theta function of this graph given by:
$\vartheta(G) = \max_{i}\frac{-N\epsilon_{i}}{-\epsilon_{i}+d-1}$?
...
1
vote
1
answer
135
views
Characterisation of walk-equivalent digraphs
Setting Let $G=(V,E)$ be an undirected graph. A walk $\pi$ in $G$ of length $k$ is a sequence of $k+1$ vertices $v_1,\ldots,v_{k+1}$ such that for each $i\in[1,k]$,
$\{v_i,v_{i+1}\}\in E$. Let $H=(W,F)...