# 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

**2**

votes

**0**answers

59 views

### On norms of Boolean functions

Let $f: \mathbb{F}_2^n \rightarrow \{-1,1\}$ be a Boolean function, represented by a $N=2^n$ dimensional vector, $f \in \{-1,+1\}^N$.
Define the Fourier transform of $f$ to be $\hat{f}$, where $$\hat{...

**0**

votes

**0**answers

43 views

### Lower bounds on the length of circuits, depending on the number of times it crosses itself

I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below.
Let $G(V,E)$ be ...

**1**

vote

**0**answers

38 views

### 4-cycles vs eigenvalue information on quasi-random graphs

My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs.
The main purpose of the paper is to show ...

**7**

votes

**0**answers

109 views

### Is this lower bound for the size of minimal vertex cover new/interesting?

I have found this lower bound for the size of minimal vertex cover (and proved it).
If a simple connected graph G on n vertices has largest and smallest eigenvalues $\lambda_1,\lambda_n$, ...

**3**

votes

**0**answers

87 views

### How related are Fourier transforms on finite groups and Fourier transforms on graphs?

Here are two generalizations of the notion of a Fourier transform. I am also aware of the Pontryagin Duality generalization for locally compact abelian groups, though I am personally more concerned ...

**4**

votes

**1**answer

108 views

### Relation of row sums to largest eigenvalue

I know that the largest eigenvalue of a graph is bounded between the minimal and maximal row sum of the matrix. If I have a $0-1$ symetric matrix (an adjacency matrix) and I know $k$ of the rows have ...

**0**

votes

**0**answers

50 views

### $\lambda_2$ of Laplacian of a regular graph

Given a $d$-regular graph $G=(V,E)$ with $|V| =n$. We know that the smallest eigenvalue of the normalized laplacian matrix of $G$ is $0$. I have seen the formulation of the second smallest eigenvalue $...

**2**

votes

**0**answers

104 views

### Number of components of self-index complementary graphs

Let $G$ be a simple graph. We say this graph is self-index complementary ($SIC$) if $\lambda_1 (G)=\lambda_1 (\overline{G})$, where $\lambda_1(G)$ denotes the index of the adjacency matrix of the ...

**0**

votes

**0**answers

34 views

### Orthogonality condition of symmetric matrix pencil

Let $P(\lambda)=\lambda M−L\in \mathbb{R}^{n \times n}$ be a matrix pencil with symmetric nonsingular matrix $M$ and $L$ is a weighted Laplacian matrix of a connected graph. Clearly $(0,1_n)$ is an ...

**1**

vote

**1**answer

67 views

### Total behaviour of graph spectrum

Let $\mathcal{G}$ be the set of all finite connected simple graphs minus the complete graphs. For any $G\in \mathcal{G}$, let $\lambda_{\geq0}(G)$ denotes the smallest positive adjacency eigenvalue of ...

**0**

votes

**0**answers

29 views

### Unions of subgraphs of quasi-random graphs

Fix a positive probability $p$, and take $G = (V, E)$ to be a graph with edge density $p$. Given a subset $S$ of $V$, take $K(S)$ to be the complete graph on the vertices in $S$.
Following Chung in ...

**2**

votes

**1**answer

99 views

### Cocktail party and tripartite graphs are DS?

Cocktail party graphs and $k_{n,n,n}$ (a tripartite graph) are determined by the spectra of their adjacency matrices? I think thay are DS ( determined by the adjacency spectrum) but I can't find a ...

**9**

votes

**3**answers

1k views

### What happens to eigenvalues when edges are removed?

I am stuck at the following :
Let $G$ be a graph and $A$ is its adjacency matrix.
Let the eigenvalues of $A$ be $\lambda_1\le \lambda_2\leq \cdots \leq \lambda_n$.
If we remove some edges from the ...

**1**

vote

**1**answer

65 views

### Anderson localization for Bernoulli potentials on half-line

Anderson localisation for (discrete) Schrödinger operators with Bernoulli potentials on $l^2(\mathbb{Z})$ was proven in
https://link.springer.com/article/10.1007/BF01210702
I am wondering if there ...

**2**

votes

**2**answers

72 views

### Question about eigenvalues of connectivity matrices for graphs [closed]

I'm a computer science student working on a research project that deals with computational study of atomic clusters. I'm using a graph based representation of the clusters using a binary connectivity ...

**1**

vote

**0**answers

65 views

### Normalized Laplacian matrix versus walk Laplacian matrix (or normalized adjacency matrix versus walk adjacency matrix)

In graphs, found that two different normalization matrices exist for Laplacian and adiacency matrix. I will ask about the adjacency matrix (for the Laplacian matrix the questions are the same). The ...

**3**

votes

**1**answer

56 views

### Reference request: maximal Cheeger constant for 3-regular graphs

Given a connected graph $G$, the Cheeger constant $h(G)$ (a.k.a. Cheeger number or isoperimetric number) roughly measures the "bottleneckedness" of $G$. See Wikipedia for the precise definition.
I ...

**10**

votes

**2**answers

270 views

### Algebraic properties of graph of chess pieces

For the purpose of this question, a chess piece is the King, Queen, Rook, Bishop or Knight of the game of chess. To a chess piece is attached a graph which represents the legal moves it can make on an ...

**0**

votes

**0**answers

19 views

### Explicit computation of spectrum of some infinite trees

This is probably more of a computational matter, but on Mathematica StackExchange they closed my question, so I try and ask here as well.
I would like to compute the spectrum of some infinite trees ...

**2**

votes

**0**answers

56 views

### Infinite trees whose spectrum has more than 3 connected components

I was wondering whether there exists any infinite tree $T$ such that the action of $\mathit{Aut}(T)$ on the set of vertices $V=V(T)$ has finitely many orbits, and whose spectrum $\sigma(T)$ has ...

**0**

votes

**1**answer

45 views

### Spectral of a connected d-regular bipartite graph [closed]

Let $G$ be a connected $d$-regular bipartite graph.
Would you please tell me about the spectrum of this graph?

**0**

votes

**0**answers

58 views

### Singular values and the chromatic number

What relation, if any, is there between the singular values of the adjacency matrix ( or possibly incidence matrix) of a simple graph and its chromatic number. Typically, do we have Hoffmann type, or ...

**2**

votes

**0**answers

145 views

### Graphs with the same Laplacian eigenvalues

Let $L$ be the
Laplacian matrix
for a simple graph $G$ of $n$ vertices,
and $\lambda_0,\ldots,\lambda_{n-1}$ its $n$ eigenvalues.
Q.
What is the cardinality of the class of $n$-vertex graphs $\...

**1**

vote

**0**answers

54 views

### Large bounded degree expanders in the hypercube

Does the $n$ dimensional hypercube graph contain large bounded degree expanders as subgraphs? For example, of exponential size in $n$?
If not, one could relax the problem and allow the maximum ...

**2**

votes

**1**answer

94 views

### Eigenfunctions adjacency operator on infinite graph in $l^2$

Let $\Gamma$ be an infinite (connected) graph without edges going from a vertex to itself (though it might have multi-edges). Let us suppose that $\Gamma$ has finite valence.
Is there always a ...

**1**

vote

**0**answers

90 views

### Digraphs with same number of semiwalks

This is a follow-up question to Characterisation of walk-equivalent digraphs.
Question: Do there exists two directed graphs $G$ and $H$ consisting of the same number ($n$) of vertices, such that
\...

**1**

vote

**1**answer

99 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)...

**2**

votes

**0**answers

230 views

### Why do we assume that $\mathcal{A}$ is an algebra in this 2003 paper of Bobkov and Tetali?

In the following paper (extended version here), at the beginning of section 3, the authors give two axioms about $\mathcal{A}$. Axiom 1 is about $\mathcal{A}$ being an algebra. I do not see where this ...

**2**

votes

**1**answer

91 views

### Two cospectral (normal) digraphs which are not orthogonal similar

Preliminaries
A complex matrix $A$ is normal when $A$ and $A^*$ commute. A real matrix $A$ is normal when $A$ and $A^t$ commute.
Two complex matrices $A$ and $B$ are said to be unitary similar if ...

**2**

votes

**1**answer

70 views

### On sum of elements in products of matrices for a simple graph

Let $G$ be a simple graph with vertex set $\{v_1,v_2,\ldots,v_n\}$. The adjacency matrix of $G$ is the 0-1 matrix
$A$, where $A_{i,j}=1$ when $v_i$ is adjacent with $v_j$. The degree matrix is the ...

**0**

votes

**0**answers

71 views

### Difference between second largest and smallest eigenvalue

The question is related to spectral graph theory. Wrt Fiedler
number and algebraic connectivity of graphs, sometimes academic literature uses second largest eigenvalue, sometimes second smallest. For ...

**1**

vote

**1**answer

205 views

### Eigenvectors of graph Laplacian for spectral clustering

I have the following questions regarding the graph Laplacian for spectral clustering:
What is the intuition behind projecting the Laplacian (D-A, where D is the degree matrix and A is the affinity ...

**1**

vote

**0**answers

80 views

### Algebraic connectivity of the path $P_n$

Let $G$ be a graph with $n$ vertices.
Denote by $L(G)$ the Laplacian matrix of $G$ and
$0=\lambda_1\leqslant\lambda_2\leqslant...\leqslant\lambda_n$ its spectrum.
The number $\lambda_2$ is called the ...

**1**

vote

**1**answer

68 views

### Spectral bound for maximum clique $k(G)$ in a permutation graph

Let $\pi \in S_n$ be an arbitrary permutation. By permutation graph, we refer to a simple graph with nodes $[n]$ and edges that connect pairs of nodes that appear sorted in $\pi$. Formally, $G=(V=[n],...

**5**

votes

**0**answers

157 views

### Can the corollary of the Ihara–Bass formula be extended to $ u^2 = 1 $?

Suppose there is a finite undirected graph $G(V,E)$ having $n$ vertices and $m$ edges.
The non-backtracking matrix $B$ is indexed by $2m$ directed edges and defined as
$$
B(a \to b, c \to d) = \delta_{...

**2**

votes

**2**answers

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

**7**

votes

**1**answer

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

**7**

votes

**1**answer

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

**1**

vote

**2**answers

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

**2**

votes

**1**answer

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

**3**

votes

**0**answers

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

**5**

votes

**2**answers

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

**1**

vote

**1**answer

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

**4**

votes

**1**answer

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

**6**

votes

**0**answers

223 views

### Is there a version of Weyl's law for graph Laplacians?

Is there a version of Weyl's law or a local Weyl's law for eigenvectors of the graph Laplacian?
For some context, a colleague in statistics has encountered eigenvectors of the Laplacian for certain ...

**1**

vote

**0**answers

134 views

### Principal eigenvector of non-negative symmetric block matrix is approximated by a linear combination of the principal eigenvectors of the blocks

Let $
M \in \mathbb{R}^{n \times n} =
\begin{bmatrix}
A & B \\
B^T & C
\end{bmatrix}
$ for some nonnegative $A \in \mathbb{R}^{k \times k}, B \in \mathbb{R}^{k \times n-k}, C \in \mathbb{R}^{n-...

**1**

vote

**0**answers

121 views

### Expander mixing lemma in combinatoric expanders

There is a well-known relation between combinatoric expansion and the gap between the first and the second largest eigenvalues (Dodziuk 1984)
:
$$ h(G) \le d \sqrt{2 (1 - \alpha)} $$
where
$$h(G) = \...

**1**

vote

**0**answers

81 views

### What is intuitive perception of $T_{\alpha_1} \circ T_{\alpha_2} \circ … \circ T_{\alpha_M} $ in graph domain?

if $G(V,E,W)$ be a weighted graph and $\vert V \vert =N $. for any vertex $i \in \lbrace 1,2,...,,N \rbrace $ define a generalized translation operator $T_i:\mathbb{R}^N \to \mathbb{R}^N $via ...

**10**

votes

**1**answer

287 views

### An upper bound for the largest Laplacian eigenvalue of a graph in terms of its diameter

Let $G$ be a simple graph with $n$ vertices and $\lambda$ be the largest eigenvalue of its Laplacian operator $L=D-A$. I have some evidence for the following conjecture:
Conjecture: If G has ...

**1**

vote

**1**answer

101 views

### Is there a transient graph whose spectral dimension two?

Let $G = (V(G), E(G))$ be an infinite connected simple graph.
Let $((S_n)_n, (P^x)_{x \in V(G)})$ be the simple random walk on $G$.
Let $p_n (x,y) = P^x (S_n = y)$.
A spectral dimension of $G$ is ...