# 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

349
questions

2
votes

1
answer

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

3
votes

0
answers

35
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

43
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

81
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

29
views

### Spectra of line graphs

What are the latest known results about spectra of finite line graphs? I just saw this paper on spectra of laplacians of infinite line graphs. Whether this is also valid for finite graphs.
Note that I ...

0
votes

0
answers

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

0
votes

0
answers

28
views

### Effect of "vertex splitting" on spectral gap

Let $\Gamma=(V,E)$ be a finite graph and let $v\in V$. Let $v\in V$ and let $\{vw_1,\ldots,vw_k\}$ be all the edges in $E$ which are incident to $v$.
Let $\Gamma'=(V',E')$ be any graph with the ...

4
votes

1
answer

103
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

101
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

113
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

59
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

120
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

45
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

89
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

118
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

73
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

182
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

113
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

384
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

75
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

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

3
votes

1
answer

221
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

116
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

235
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

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

3
votes

0
answers

123
views

### Spectral norm and "operator norm" for hypergraphs

Consider a $d$-regular, $k$-uniform hypergraph: the elements $S$ of its set $E$ of edges are subsets of $V$ of size $k$, and each vertex $v\in V$ is in $d$ edges. We can then define its adjacency ...

3
votes

1
answer

79
views

### On cospectral graphs

Is there examples of non-isomorphic cospectral graphs having
Non-isomorphic automorphism groups?
Isomorphic automorphism groups?

1
vote

1
answer

76
views

### Non-regular cospectral graphs with same degree sequences

I am looking for a large family (infinite pairs) of cospectral graphs with these condtions:
The graphs are non-regular,
Minimum degree is greater than $1$,
The degree sequences of these cospectral ...

1
vote

0
answers

43
views

### What are the meaning of left singular vectors of an incident matrix?

Consider a graph G and its incident matrix $B\in R^{m\times n}$. We can compute the SVD of $B$ as $B=U^{\top}\Sigma V$. Note that the Laplacian matrix $L_G=B^{\top}B$, so the right singular vectors ...

3
votes

1
answer

129
views

### Reference request: Spectrum of intersection matrices

Let $P(A)$ be the set of all non-empty proper subsets of a finite set $A$. Let $M$ be a matrix indexed by the set in $P(A)$ whose $ij$ the entry is $1$ if the associated sets are disjoint and $0$ ...

1
vote

0
answers

78
views

### Delocalization of eigenvectors of graph Laplacians

Let $(V,E)$ be an undirected, connected graph with $n$ nodes. The graph Laplacian is defined as $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_1 < \...

34
votes

1
answer

568
views

### Which graphs on $n$ vertices have the largest determinant?

This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc.
The determinant of ...

1
vote

0
answers

90
views

### Varieties determined by a characteristic-type of polynomial with the structure of an underlying graph

While writing my master thesis, following problem came up:
Given a digraph $G$ with edges $e_1,..,e_n$ and a
given a $n\times n$- matrix $A\in\mathbb{C}^{n\times n}$ such that $A_{ij}=0$ if the ending ...

2
votes

0
answers

38
views

### Formulas to determine the value of graph energy with addition or deletion of edges

If $G$ is a graph, then the graph energy of $G$ denoted by $E(G)$ is defined as the sum of absolute values of eigenvalues of the adjacency matrix of $G$. It is known that $E(G)\geq E(G-v)$, where $ ...

0
votes

0
answers

45
views

### How can I find family of non-isomorphic graphs with specific properties?

I asked this question:
How to find non-isomorphic graphs with specific orders?
Two new questions have arisen for me.
I have a graph, $G$, with $2n$ vertices. It has one connected component of order $...

3
votes

1
answer

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

0
votes

0
answers

117
views

### Closed non-backtracking walks and eigenvalues of the adjacency matrix in non-regular graphs

Let $\Gamma$ be an undirected finite graph. Write $M_r$ for the number of non-backtracking closed walks of length $r$ in $\Gamma$, i.e., walks where a step is never
followed by its inverse. Let $A$ be ...

2
votes

0
answers

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

0
votes

1
answer

74
views

### If there are eigenvectors with largest components $i$ resp. $j$, then is there an eigenvector with two largest components $i$ and $j$?

Let $G=(V,E)$ be a connected (finite simple) graph with vertex set $V=\{1,...,n\}$ and let $\theta_2\in\Bbb R$ be the second-largest eigenvalue of its adjacency matrix. I wonder about the following ...

2
votes

0
answers

96
views

### The rank of a Laplacian-type matrix

Suppose that $M$ is an integer, symmetric matrix of order $n>2$ with the positive integers $K_1,\dotsc,K_n$ on its main diagonal, and with all the off-diagonal elements equal to $0$ or $1$ so that ...

13
votes

1
answer

442
views

### $\ell^1$-norm of eigenvectors of Erdős-Renyi Graphs

Setting. Let $G(n,p)$ denote the usual Erdős-Renyi (random) graphs. For each such graph there is an associated Laplacian matrix $L = D - A$ where $D$ collects the degrees on the diagonal and $A$ is ...

0
votes

0
answers

142
views

### How is the second smallest eigenvalue of normalized laplacian bounded for random graphs?

It is well known that for any graph G following holds
$\frac{\lambda_2}{2} ≤ \phi(G) ≤ \sqrt{2\lambda_2}$, where $\phi(G)$ is the conductance of the graph and $\lambda_2$ is the second smallest ...

4
votes

0
answers

131
views

### Relation between two conjectures on reconstruction of graphs

In spectral graph theory, there is a conjecture that claims: Almost every graph is determined by its adjacency spectrum ($DS$). This conjecture belongs to professor Willem Haemers.
Also, we have a ...

3
votes

1
answer

102
views

### Spectral properties of half-transitive graphs

The half-transitive graphs form a curious class of graphs with some kind of intermediate symmetry that is non-trivial to achieve. More precisely, a graph is half-transitive if its symmetry group is
...

11
votes

1
answer

417
views

### Is there Matrix-Tree theorem for counting the bases of a connected matroid?

The famous Kirchhoff's Matrix-Tree theorem counts the number of spanning trees of a connected graph, that is, the number of bases of its cycle matroid. But it appeals to vertices, that's why I do not ...

74
votes

4
answers

11k
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”. ...

2
votes

0
answers

118
views

### Expansion of random subgraphs of a bi-regular bipartite graph

Let $G = (L, R, E)$ be a bi-regular bipartite graph, with $|L|=n$ and $|R| = C \cdot n$, where $C$ is a large constant. Let $d$ be its (constant) right-degree.
We know $G$ is a good spectral expander. ...

24
votes

6
answers

1k
views

### Factorization of the characteristic polynomial of the adjacency matrix of a graph

Let $G$ be a regular graph of valence $d$ with finitely many vertices, let $A_G$ be its adjacency matrix, and let $$P_G(X)=\det(X-A_G)\in\mathbb{Z}[X]$$ be the adjacency polynomial of $G$, i.e., the ...

3
votes

1
answer

242
views

### Sums over products over short paths in an expander graph

Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with ...

3
votes

0
answers

248
views

### Eigenvalue bounds and triple (and quadruple, etc.) products

Very basic and somewhat open-ended question:
Let $A$ be a symmetric operator on functions $f:X\to \mathbb{R}$, where $X$ is a finite
set. Assume that the $L^2\to L^2$ norm of $A$ is $\leq \epsilon$, i....