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
415 questions
4
votes
1
answer
303
views
Minimum eigenvalue of a symmetric matrix
I was solving a problem and got stuck on the following:
Let $[p] = \{1, \ldots, p\}$ where $p \in \mathbb{N}$. Let $P(n, r)$ denote the set of all injective functions from $[r]$ to $[n]$ and write a ...
- 41
4
votes
1
answer
252
views
What is the resistance between two vertices on the Hanoi-towers graph?
The Hanoi graph $H^n_k$ is the graph with nodes representing states of a Hanoi puzzle with $n$ discs and $k$ pegs, and edges representing the various moves of the discs from peg to peg.
The Hanoi ...
- 2,185
1
vote
0
answers
100
views
PageRank in directed graphs: equivalence of iterative and eigenvalue methods
Given a directed graph $ G $ with $ n $ nodes, we can represent this graph using an adjacency matrix $ A $. The stochastic matrix $ S $ can be derived from the adjacency matrix using the following ...
- 4,058
3
votes
0
answers
61
views
Is this bipartite equivalent of 1-walk-regular graphs known?
A graph $G$ is 1-walk-regular if
for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$.
for each edge $vw$ the number of ...
- 13.6k
0
votes
0
answers
15
views
Change in two spectral deviations due to edge deletion in a signed graph
Prove (or disprove) the following. Let $\Sigma=(G,\sigma)$ be a given signed graph. If $\lambda_1\ge\lambda_2\ge\cdots\ge \lambda_n$ and $\mu_1\ge\mu_2\ge\cdots \ge \mu_n$ are the eigenvalues of the ...
- 61
1
vote
0
answers
61
views
Eigenvalues and eigenvectors of the path Laplacian
Consider the Laplacian matrix of the path graph:
$$
L = \begin{bmatrix}
1 & -1 & 0 & \cdots & 0 & 0\\
-1 & 2 & -1 & \cdots & 0 & 0\\
0 & -1 & 2 & \...
- 11
0
votes
0
answers
16
views
Representing a periodic strip operator as a tensor product of operators
I hope this question is not trivial, but here goes. I want to consider a bounded operator on $\mathcal{H}=\ell^2(\mathbb{Z}\times \{0,...,N-1\})$ that is a discrete Schrodinger like operator.
...
- 633
0
votes
1
answer
73
views
Computing spectrum of very simple Schrödinger operator
I asked this question recently on a thread in math stack exchange, but with no real answers suggested. I think this is a relatively simple variation on the classical free Laplacian spectrum, so I ...
- 633
4
votes
2
answers
282
views
Multiplicity of the smallest non-zero Laplacian eigenvalue for tree graphs
How accurate is the following statement: "For tree graphs, the multiplicity of the smallest non-zero eigenvalue $\lambda_2$ of the Laplacian is 1." If not valid, in which cases does it fail ...
- 91
4
votes
1
answer
103
views
When do the nonzero eigenvalues of a directed graph Laplacian have the same absolute value?
Question: Let $G$ be a strongly connected directed graph on $n$ vertices with Laplacian $L(G)$. Then $L(G)$ has one zero eigenvalue $\lambda_1=0$ and $n-1$ nonzero eigenvalues $\lambda_2,\ldots,\...
- 145
0
votes
0
answers
25
views
How to prove the signless Laplacian polynomial is reconstructible?
On page 253 in the book "An Introduction to the Theory of Graph Spetra" by Cvetkovic, Rowlinson and Simic, the authors write "We mention in passing that the $Q$-polynomial of a graph is ...
- 103
1
vote
0
answers
19
views
How to prove two non-isomorphic strongly regular graphs are not Seidel switching isomorphic?
It is known that $L(K_{4,4})$ and the Shrikhande graph are two non-isomorphic strongly regular graphs but they are Seidel switching isomorphic.(Cvetknvic-Rowlinson-Simic An Introduction to the Theory ...
- 103
4
votes
2
answers
219
views
Existence of disjoint expanders in a graph
Let $n$ be some sufficiently large positive integer and let $V$ be a set of $n$ vertices. Are there always disjoint sets of edges $E_1,\ldots, E_{\log n}$ such that $G_i = (V,E_i), \forall i = 1,\...
- 173
3
votes
0
answers
128
views
Spectra of Coxeter diagrams and representations of Coxeter groups
Let $S$ be a Coxeter diagram, i.e. an unoriented graph, edges labelled by weights $3,4,5,...$ . This includes (affine) Dynkin diagrams,
Then
Theorem 3.1.3 of Brouwer and Haemers' Spectral Graph ...
- 5,701
0
votes
0
answers
92
views
Second largest eigenvalue of graph
Let $G$ be a connected $d$-regular n-vertex graph and let $k:= k(n)\in \mathbb{N}.$ Given a Non-empty set of vertices $\phi\neq B\subseteq V(G),$ how can I prove that all but at most $\frac{\lambda_2|...
- 53
0
votes
1
answer
131
views
Function of eigenvalues of Laplacian matrix
Let $G$ be a simple $n$-vertex graph and let $\mu_n\geq\mu_{n-1}\geq\dots\geq\mu_1$ be the eigenvalues of its Laplacian matrix, how can I find a function $$f(\mu_1,\mu_2,\dots\mu_n) \text{ such that } ...
- 53
3
votes
0
answers
92
views
Inverse of adjacency matrix of overlapping cycle graphs?
Consider a graph composed of two overlapping cycles: one cycle of length $\ell$ and one cycle of length $m$ where the two cycles share $e$ edges. See picture as an example:
The eigenvalues and ...
- 274
0
votes
1
answer
106
views
Spectral theory: a key to unlocking efficient insights in network datasets
In the context of directed or undirected graphs, matrices such as adjacency and Laplacian matrices are commonly used. The eigenbasis of these matrices addresses some practical implications, such as ...
- 4,058
0
votes
0
answers
64
views
triangle free cubic graphs
Is there any classification of cubic triangle-free graphs? Which structural properties of cubic triangle-free graphs are known? How about their eigenvalues or any other useful properties?
- 105
2
votes
0
answers
126
views
A reference for high girth expander graphs
I'm looking for a reference to the existence of family of constant (or bounded by constant) degree graphs which are both high-girth (meaning the ratio girth/diameter is uniformly bounded from below by ...
- 401
7
votes
3
answers
671
views
Real-world examples of unweighted directed graphs
Social Networks, Internet Traffic, Citation Networks, Transportation Networks, and Biological Networks exemplify real-world instances of unweighted directed graphs. Within these domains, the Graph ...
- 4,058
0
votes
0
answers
36
views
A class of directed graph, when their minimal polynomial of the adjacency matrix matches the characteristic polynomial
We consider an unweighted directed simple graph, $G$, with a Hamiltonian cycle.
Q. Assume that the adjacency matrix of $G$ is non-singular. Do the characteristic and minimal polynomials of the ...
- 4,058
1
vote
2
answers
198
views
Topology of directed graph $G$ with non-singular adjacency matrix
Given a directed graph $G$ with non-singular adjacency matrix,
Q. Is there a directed
subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...
- 4,058
0
votes
0
answers
69
views
How can I measure similarity between two graphs with identical topology but different edge weights
I have two graphs, G1 and G2, with exactly the same topology. Their only difference lies in the edge weights, which vary between 0 and 1.
How can I measure the similarity between G1 and G2 under these ...
- 1
2
votes
1
answer
94
views
Testing for equal characteristic polynomials using a single determinant calculation
Let $A_1,A_2$ be $n\times n$ symmetric matrices over $\{0,1\}$, and let $p_1, p_2$ be their respective characteristic polynomials over the rationals.
If $p_1 \ne p_2$, then there is some positive ...
- 37.7k
3
votes
1
answer
241
views
Some questions about induced subgraphs of the directed hypercube graph
Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
- 129
2
votes
0
answers
81
views
Given a low-rank symmetric positive semidefinite matrix and a basis of its nullspace, is there a fast way to get the nonzero eigenvalues?
I have a (possibly dense) $k\times k$ real matrix $L = AA^T + B^T B$, a type of combinatorial Laplacian (self-adjoint, symmetric, positive semidefinite) of rank $(k-n)$ and possibly repeated nonzero ...
- 21
2
votes
1
answer
140
views
Invertibility of message passing with invertible parametrization
Consider the message passing framework defined by, $$f(\boldsymbol{x}_i)= \boldsymbol{x}_i + \sum_{j \neq i} (\boldsymbol{x}_i -\boldsymbol{x}_j) g(\|\boldsymbol{x}_i -\boldsymbol{x}_j\|^2),$$ for $i=...
2
votes
0
answers
97
views
Bound on the magnitude of the entries of the Laplacian pseudo-inverse
Let $L$ be the laplacian matrix of a connected graph $G$ with real positive weights and $N$ vertices, or that can be assumed to have binary weights for simplicity.My goal is to bound $\Vert L^+\Vert_{\...
- 21
3
votes
0
answers
74
views
Second eigenvalue of primitive matrix
Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$.
The ...
- 143
0
votes
1
answer
82
views
Number of bi-directional (or symmetric edges) [closed]
I am trying to figure out the least number of directed edges that would be bi-directional after constructing a graph with $2k-1$ nodes that are each $k$ in-degree. For example, $2(2)-1=3$ nodes that ...
- 1
2
votes
0
answers
55
views
Regularize a graph while embedding the spectrum of adjacency matrix
Given an irregular graph $G$ whose maximum degree is $d$, I am interested in producing a new graph $G'$ which is regular and has the spectrum of the adjacency spectrum of $G$ embedded in the spectrum ...
- 21
1
vote
0
answers
91
views
Diameters of random bipartite graphs
Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
- 11
2
votes
1
answer
292
views
Do balls in expander graphs have small expansion?
Consider a $d$-regular infinite transitive expander graph $G$, and let $B_r$ be a ball of radius $r$ in $G$. Can one place any upper bounds on the expansion of $B_r$?
My intuition is that $B_r$ will ...
- 31
2
votes
0
answers
187
views
Max-cut from Laplacian
(This question seems like very standard material for those well-versed in the subject. I thought I would get a quick answer from Math stackexchange, but to no avail.)
Given a weighted graph with $n$ ...
- 511
3
votes
0
answers
84
views
Clique number and spectrum of a graph
In the Wikipedia article on Grassmann graph it is stated that in this graph:
$$\omega=1-\frac{\lambda_{max}}{\lambda_{min}}$$
where $\omega$ is the clique number of the graph, and $\lambda_{max}$ and $...
- 175
1
vote
1
answer
177
views
Spectral characterization of complete or complete bipartite graphs
The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs:
Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
- 243
1
vote
0
answers
50
views
Bounds on the spectral radius of a perturbed directed graph
Suppose $(G_n)$ is a sequence of strongly connected directed graphs (without multiple edges) with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be ...
- 11
8
votes
1
answer
241
views
Is there a bipartite graph with $\sqrt{2}$ as an eigenvalue with high multiplicity, specifically more than in the Heawood graph?
The Heawood graph is a $3$-regular graph on $14$ vertices. Its (adjacency) spectrum is $\{ (3)^1, (\sqrt{2})^6, (-\sqrt{2})^6, (-3)^1 \}$. So, $3/7 \approx 42.8\%$ of its eigenvalues equal $\sqrt{2}$.
...
- 1,446
1
vote
0
answers
54
views
Controlling quantity related to Laplacian pseudo-inverse of Erdős–Rényi graph
Consider an $n$-node undirected graph $G = (V, E)$ equipped with weights $W$. Let $L$ be the weighted graph Laplacian matrix, i.e. $L_{ij} = -W_{(i,j)}$ for $(i,j)\in E$ and $L_{ii} = \sum_{j:(i,j)\in ...
- 11
2
votes
0
answers
146
views
Graph Laplacians, Riemannian manifolds, and object collisions
To preface this question, I am a part-time game developer and full-time optimization fiend.
I am working on object collisions at the moment and many resources I have found online are more-or-less just ...
- 21
2
votes
0
answers
63
views
Tightness of the bounding the operator norm of graph by average degree from below
Let $G = (V,E)$ be a simple graph with adjacency matrix $A$. It is well known that the largest eigenvalue
$\lambda_{1}$ of $A$ is contained within the interval $[d, D]$ where $d$ is the average degree ...
- 401
3
votes
1
answer
148
views
Spectrum of the adjacency matrix of certain directed graphs
For an undirected graph $G$, its adjacency matrix $A_G$ is symmetric, and by the (consequence of) spectral theorem, each of its Jordan blocks has size $1$. This is not true for a general directed ...
- 161
7
votes
1
answer
382
views
Diameter bound for graphs: spectral and random walk versions
This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and ...
5
votes
0
answers
121
views
The Smith decomposition of the graph Laplacian and Locality
Let $X$ be a graph. Let $V(X)$ and $E(X)$ be the sets of vertices and edges of the graph respectively. If $f:V(X) \rightarrow G$ where $G$ is an abelian group, then one can define a graph Laplacian as ...
- 51
0
votes
0
answers
83
views
When is the sum of matrices (circulant + [super upper triangular]) not diagonalizable?
By the circulant matrix $C \in M_n(\mathbb{R})$, we mean that
$$ C = \left[\begin{array}{c|c|c|c} e_n & e_1 & \cdots & e_{n-1} \end{array}\right] $$
where $e_1,\dots,e_n$ are the standard ...
- 4,058
2
votes
1
answer
133
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=\...
- 4,058
1
vote
1
answer
198
views
Directed graph whose adjacency matrix admits only 0 as eigenvalue
Let $G$ be a directed graph and let $P_i$
be its vertices. Let $A$
be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$
if and only if there is a directed edge from $P_i$
to $P_j$, ($a_{i,...
- 4,058
6
votes
1
answer
515
views
Non-diagonalizability of the adjacency matrix of a directed graph
Let $G$ be a directed graph with no multiple edges or loops and let $P_i$ be its vertices. Let $A$ be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$ if and only if there is a directed ...
- 4,058
0
votes
1
answer
116
views
Two fractionally isomorphic graphs but only one having eigenvalue zero
I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) with adjacency matrices $A_G$ and $A_H$, respectively, such that
$G$ and $H$ are ...
- 493