# 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

375
questions

0
votes

0
answers

44
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 ...

2
votes

1
answer

99
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=\...

1
vote

1
answer

57
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,...

6
votes

1
answer

297
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 ...

0
votes

1
answer

92
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 ...

4
votes

1
answer

76
views

### Strongly/distance regular graphs over $\mathbb{Z}_2^n$ with the same parameters

I am wondering if there is a known example of a pair of non-isomorphic graphs $G$ and $H$ that are both Cayley graphs for $\mathbb{Z}_2^n$ (for some $n$) and are both distance regular and have the ...

0
votes

0
answers

22
views

### Relation between the left-dominant eigenvectors (eigenvector corresponding to 0 eigenvalue) of two Laplacian matrices

Let $G_1=(v,\epsilon_1)$,$G_2=(v,\epsilon_2)$ be two graphs with the same set of vertices and $\epsilon_1 \subset \epsilon_2$. $L_1$ and $L_2$ be the Laplacian matrices associated with graph $G_1$ and ...

0
votes

0
answers

107
views

### On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph

Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...

5
votes

1
answer

96
views

### Can we calculate the spectral radius of the universal cover for specific graphs?

Background
For a finite graph $G$, let $\tilde{G}$ denote the universal cover of $G$. For a vertex $v$, let $p_{2n}(v)$ denote the number of paths of length $2n$ that start and end at $v$. The ...

1
vote

0
answers

44
views

### What do you call this class of matrices with a unique positive eigenvalue associated to a graph?

I am looking for the name of a class of symmetric matrices $M\in\Bbb R^{n\times n}$ that I can associate to a (finite simple) graph $G=(V,E)$ with $V=\{1,...,n\}$ and that have the following ...

5
votes

0
answers

129
views

### (How) does the spectral gap of the $n\times n$ Rubik's cube close with $n$?

Consider the spectrum of the adjacency matrix $A$ of the Cayley graph of the standard, 3x3x3 Rubik's cube generated with the usual quarter-turn and half-turn twists of each face (the Singmaster ...

0
votes

0
answers

43
views

### Comparing spectral radius of two graphs using the entry of Perron vector

Suppose we have a graph $G$.
Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector.
Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$.
We ...

8
votes

0
answers

170
views

### Explicit constructions of Ramanujan graphs

I am trying to find a list of all the explicit constructions of Ramanujan graphs. By a Ramanujan graph I mean a $k$-regular multi-graph $G$ such that all the non-trivial eigenvalues $\lambda$ of the ...

0
votes

0
answers

26
views

### Nilpotent parts of graph Laplacians

Let $W$ be the adjacency matrix of a directed graph. Let us denote by $D$ the associated in-degree matrix, whose diagonal entries are given by $D_{ii} = \sum_j W_{ij}$. The associated Laplacian
$$ L =...

0
votes

1
answer

219
views

### Vertex degree on random graphs

Let $p = d/n$ with $d$ constant. How do I prove that, with high probability, $G_{n,p}$ contains a vertex of degree at least $(\log n)^{1/2}$,
where $G_{n,p}$ is a graph with $n$ vertices and the ...

1
vote

1
answer

87
views

### Eigenvalues of directed graph with one outward edge for each vertex

I am concerned with unweighted directed graphs where each node contains exactly one edge pointing to another node, which could be itself. In other words, each row of the adjacency matrix contains one ...

0
votes

1
answer

80
views

### Entropy of eigenvectors of (traceless) laplacian of a bipartite graph

This problem is motivated by the edge states that sometimes appear (and sometimes not) at the level of Huckel hamiltonians for $\pi$-conjugated benzenoid hydrocarbons. If this sentence is cryptic, ...

0
votes

1
answer

170
views

### Series analyzed in Lubotzky–Phillips–Sarnak "Ramanujan Graphs"

In the LPS paper "Ramanujan graphs" the adjacency matrix of $X^{p,q}$, for simplicity say that $p,q\equiv1\mod{4}$ and $\left(\frac{p}{q}\right)=1$ (so, nonbipartite) and $n=\lvert X^{p,q}\...

0
votes

0
answers

44
views

### State-of-the-art for approximating the Cheeger constant (for graphs)

What is the state-of-the-art algorithm for approximating the Cheeger constant, given a regular graph? Ideally, such an algorithm would run in polynomial time (in the size of the graph, and could be ...

0
votes

0
answers

28
views

### upper band for the eigenvalue-distance from an eigenvalue regarding its eigenvector extension, in the adjacency matrix of a local graph?

Background: Suppose we have a system in which an electron can hop locally on this lattice. Here locally means that the electron can hop up to a short distance. We can make an energy spectrum that ...

2
votes

1
answer

191
views

### Relation between spectra of a Cayley graph of a group and irreducible characters of that group

I know the following fact:
If $G$ is an abelian group and $S\subset G$ be a subset of G such that $1\notin G$ and $S=S^{-1}$ and we draw an edge between $g$ and $h$ if and only if $hg^{-1}\in S$,then ...

0
votes

0
answers

118
views

### Non-backtracking operator and spectra

Let $A$ be the adjacency operator of a symmetric graph $\Gamma$. (It may be weighted and/or non-regular, but, to keep it simple, let us say it is unweighted and regular of degree $d$.) We want to ...

0
votes

0
answers

70
views

### Reference request: Spectral gap for cubic random graphs

I gather the following is well known:
Fact: There exists some $\epsilon>0$ such that with probability approaching $1$ as $n\to\infty$, a random cubic (i.e. $3$-regular) graph on $n$ vertices has ...

7
votes

0
answers

175
views

### Surprising symmetry in the Ramanujan bound

The condition for a connected $(q+1)$-regular graph to be Ramanujan is that every nonzero eigenvalue $\lambda$ of the graph Laplacian satisfy
$$q+1-2\sqrt{q}\le \lambda\le q+1+2\sqrt{q}.$$
With a ...

7
votes

0
answers

98
views

### Conceptual explanation for the gap in the spectrum of biregular trees

Ramanujan graphs are defined as $(q+1)$-regular graphs for which all nontrivial eigenvalues of the adjacency operator are contained in the interval
$$[-2\sqrt{q}, 2\sqrt{q}].$$
The reason for this ...

0
votes

0
answers

65
views

### Vertex percolation on bipartite graphs

This is essentially a repost of this math overflow post since it didn't get any reception.
Let $G = (V \cup C, \mathcal{E})$ be $(\gamma_V, \delta_A, \gamma_B, \delta_B)$-left-right-expanding with ...

1
vote

0
answers

69
views

### Graph energy and spectral radius

Suppose $G$ is a simple graph of order $n$ with eigenvalues $\lambda_1\geq \cdots\geq \lambda_n$. I've encountered the quantity $L=\big\vert |\lambda_1|-|\lambda_2|-\cdots-|\lambda_n|\big\vert$. Note ...

2
votes

1
answer

75
views

### Counting Euler circuits through labelled trees where $v_1$ and $v_2$ have distance two

Let $T_n$ be the set of all labelled trees with $n$ vertices. For any $T \in T_n$ let $D(T)$ be the 'doubled tree', where each edge of $T$ is replaced by one directed edge in each direction. $D(T)$ is ...

4
votes

0
answers

86
views

### Derivative of characteristic polynomial of a graph and derivative of characteristic polynomial of a vertex-deleted subgraph have a common root

Let $G$ be a simple graph and $G-i$ be one of its vertex-deleted subgraphs. Let $\phi(G,x)$ and $\phi(G-i,x)$ be the characteristic polynomials of $G$ and of $G-i$ respectively, with respect to their ...

1
vote

0
answers

54
views

### Angles between edges of a geometric graph and graph invariants

Are there any clever ways in which the angles between edges in a geometric graph are encoded in the graph spectrum, or another object associated with the graph?
I'm interested to see what else is ...

0
votes

0
answers

98
views

### Does an extension of the B.E.S.T. theorem for multiple Eulerian circuits exist?

Given a directed multigraph $G=(V,E)$ (multiple edges and loops are permitted) the number of distinct Eulerian circuits for $G$ can be calculated with the B.E.S.T. theorem. Does a similar theory for ...

0
votes

0
answers

45
views

### Variation in eigenvalues of adjacency matrices of regular graphs

What is known about the range of spectra of regular graphs? That is, I wish to know the largest intervals in which the minimum and maximum eigenvalues of a graph lie. For example, it is known that the ...

4
votes

1
answer

144
views

### Explicit constructions of regular graphs with very sparse induced subgraphs

Let $d\ge 3$ be a constant. Is there an explicit construction of an infinite family of $d$-regular graphs such that for $G$ in this family with $n$ vertices, every subgraph $H$ of on at most $\alpha n$...

2
votes

2
answers

131
views

### Ramanujan graphs from varieties over finite fields

Let $G$ be a $d$-regular graph. Let $d= \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge -d $ be the eigenvalues of the adjacency matrix of $G$, and set $\lambda = \max (|\lambda_2| , |\lambda_n|) $...

0
votes

1
answer

120
views

### Is there a notion of "rapid" expansion for graphs?

I'll be as intuitive and hand-wavy as possible so as to get to what I am looking for.
Suppose we have a graph $G=(V,E)$. One notion of expansion, namely vertex expansion, can be intuitively described ...

2
votes

1
answer

82
views

### Are the eigenvalues of the 1D lattice with random weights known?

Consider the adjacency matrix $\mathbf{A}$ of a one dimensional lattice of size $N$. That is, $A$ is a $N\times N$ matrix with $A_{ij}=1$ if vertex $i$ adjacent to vertex $j$ (there exists an edge ...

4
votes

0
answers

141
views

### Can resolution of the Kadison-Singer Problem provide progress on the Komlos Conjecture?

This is not a concrete question, just some thoughts.
The Komlos Conjecture is as follows-
There exists an absolute constant $C>0$, such that the following holds:
For all $d$ and any set of vectors ...

0
votes

0
answers

159
views

### compare two graphs with different number of nodes

Is there a distance measure between two graphs with different number of nodes?
To be specific, let $W_1$ and $W_2$ be their adjacency matrices respectively. When the two graphs have the same number of ...

1
vote

0
answers

97
views

### Do I need to find a maximum matching to get the matching number of a graph?

Let’s say we are talking about a simple undirected graph with no loops and no multiple edges. But not necessarily bipartite. And we need to find its matching number. Do we have to find a maximum ...

2
votes

0
answers

226
views

### Spectral norm bound for lower triangular matrix

Let $A$ be a $0/1$ square matrix which can be permuted to a non singular or a singular lower triangular matrix. Determinant is either $0$ or $1$. Can we provide tighter upper bounds on its spectral ...

1
vote

0
answers

139
views

### What is a good algorithm to measure similarity between isomorphic graphs with different node labels?

I am using graphs to represent some structured data. In my case, I have a time series of undirected unweighted graphs with the same topology (i.e. isomorphic graphs with same number of nodes and edges,...

1
vote

1
answer

258
views

### Trace minimization for generalized eigenvalue problem

In [1], it is shown in theorem 1.2 that for symmetric $n \times n$ matrices $A$, $B$, we have
$$
\min_{Y \in Y^*} \text{tr}(Y^TAY) =
\text{tr}(X^TAX) =
\sum_{i=1}^p \lambda_i,
$$
with
$$
\text{
$X^...

2
votes

1
answer

142
views

### Minimal Laplacian spread of a graph

Laplacian spread of a graph is the difference among the largest and the second smallest Laplacian eigenvalue of the graph. Is there any result or conjecture that discusses about the graphs having ...

8
votes

0
answers

389
views

### Bounding eigenvalues by taking high powers of matrices: history?

Let $A$ be real symmetric matrix. It is a well-known observation that we can bound any eigenvalue $\lambda$ of $A$ by using the fact that
$$\lambda^{2 k} \leq \textrm{Tr} A^{2 k}$$
for any $k\geq 1$. ...

0
votes

0
answers

85
views

### Incidence matrix of a planar graph

Are there any special properties for the incidence matrix when a graph is planar?

1
vote

1
answer

117
views

### Incidence matrix in a graph, meaning of $B^TB$

If $B\in\mathbb{R}^{n\times e}$ is the incidence matrix corresponding to a graph with $n$ vertices and $e$ edges, we know that $BB^T\in\mathbb{R}^{n\times n}$ is the graph Laplacian matrix.
I am ...

5
votes

1
answer

374
views

### Relationship between spectral gaps of adjacency and Laplacian matrices of graphs

Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).
Let $A$ be ...

2
votes

1
answer

162
views

### The complexity of expansion ratio (Cheeger constant) of a graph

Let $G=(V(G), E(G))$ be a graph on $n$ vertices and let $S$ be a subset of $V(G)$. The boundary of $S$, denoted by $\partial S$, is the set of edges $(i, j)$ such that $i \in S$ and $j \in V(G) \...

6
votes

1
answer

279
views

### Determinant of walk matrix for a skew-symmetric matrix of even order

Let $S=(s_{ij})$ be a skew-symmetric integral matrix of order $n$. We only consider the case that $n$ is even. Let $e$ be the all-one vector in $\mathbb{R}^n$. Define the walk matrix $$W(S)=[e,Se,\...

7
votes

1
answer

762
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}.$$
(...