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

Filter by
Sorted by
Tagged with
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 ...
Claus's user avatar
  • 6,767
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. ...
GraphX's user avatar
  • 260
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 ...
Paul Siegel's user avatar
  • 28.7k
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 ...
John D. Cook's user avatar
  • 5,147
9 votes
3 answers
344 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 ...
Clive elphick's user avatar
7 votes
1 answer
937 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}.$$ (...
H A Helfgott's user avatar
  • 19.3k
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 ...
Paul Siegel's user avatar
  • 28.7k
5 votes
1 answer
431 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-...
Elle Najt's user avatar
  • 1,422
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 ...
Vass's user avatar
  • 197
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”. ...
Claus's user avatar
  • 6,767
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 ...
Marcin Kotowski's user avatar
17 votes
1 answer
590 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 ...
Claus's user avatar
  • 6,767
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 ≥ ...
Robin Saunders's user avatar
8 votes
3 answers
481 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 ...
Xiaoyu He's user avatar
  • 1,151
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 ...
Delio Mugnolo's user avatar
7 votes
1 answer
910 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$ ...
David Bevan's user avatar
7 votes
1 answer
335 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$ ...
Sirolf's user avatar
  • 493
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 ...
user3275957's user avatar
6 votes
3 answers
428 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 $\...
Patt Geffrey's user avatar
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.
Turbo's user avatar
  • 13.6k
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 ...
042's user avatar
  • 83
5 votes
1 answer
422 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 ...
Marcin Kotowski's user avatar
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 ...
Felix Goldberg's user avatar
5 votes
1 answer
143 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 ...
Clive elphick's user avatar
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 ...
Shahrooz's user avatar
  • 4,738
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 ...
Robin Saunders's user avatar
5 votes
0 answers
361 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 ...
Clive elphick's user avatar
4 votes
1 answer
511 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 ...
H A Helfgott's user avatar
  • 19.3k
4 votes
1 answer
646 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 ...
Student's user avatar
  • 555
4 votes
1 answer
940 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 ...
marco polo's user avatar
4 votes
0 answers
589 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 ...
user6818's user avatar
  • 1,883
3 votes
1 answer
154 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 ...
Felix Goldberg's user avatar
3 votes
1 answer
652 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 ...
user6818's user avatar
  • 1,883
3 votes
1 answer
166 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}...
N math's user avatar
  • 219
3 votes
0 answers
234 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 ...
Elle Najt's user avatar
  • 1,422
2 votes
3 answers
657 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)$ $...
Shahrooz's user avatar
  • 4,738
2 votes
1 answer
122 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=\...
ABB's user avatar
  • 3,898
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^...
Rafael L. Greenblatt's user avatar
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 ...
H A Helfgott's user avatar
  • 19.3k
2 votes
0 answers
55 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 $\...
M. Winter's user avatar
  • 12.5k
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}$? ...
Turbo's user avatar
  • 13.6k
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} \|...
ARG's user avatar
  • 4,342
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)...
Sirolf's user avatar
  • 493