# 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

329
questions

**6**

votes

**1**answer

165 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

374 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

102 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

68 views

### On cospectral graphs

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

**1**

vote

**1**answer

55 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

35 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

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

**0**

votes

**0**answers

31 views

### Gaussian maxima, graph connectivity, superconcentration and mean outsourcing : reference request

Consider a sequence (indexed by $n$) of centred multivariate Gaussian arrays $\{X_i\}_{i\le n}$ such that $\operatorname{Var}(X_i)=1$ for all $i$ and $\sum_{i\le n}\mathbb{E}(X_iX_j)=c_n$ for all $j$.
...

**1**

vote

**0**answers

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

**33**

votes

**1**answer

464 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

82 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

35 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

42 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

126 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

97 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

136 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

65 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

61 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

336 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

68 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

125 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

92 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

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

**71**

votes

**4**answers

8k 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

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

**23**

votes

**5**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

223 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

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

**10**

votes

**1**answer

627 views

### Eigenvalues of the complement of a graph

Let $A$ and $\widetilde A$ be the adjacency matrices of a graph $G$ and of its complement, respectively.
Is there any relation between the eigenvalues of $A + \widetilde A$ and the eigenvalues of $A$ ...

**17**

votes

**1**answer

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

**54**

votes

**5**answers

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

**0**

votes

**0**answers

28 views

### Spectral gap of continuous-time Markov chain on nonnegative integers: The geometric long indel length chain

Let $S=\mathbb Z_{\ge0}$ be the nonnegative integers, and let $T=\mathbb R_{\ge0}$ be the nonnegative real numbers. Next, let $\gamma\in(0,1),r\in(0,1),$ and let $Q=(Q_{n,m})_{n,m\in S}$ be such that ...

**5**

votes

**1**answer

232 views

### Finding zero-one vectors in the row space of a matrix

Suppose that $M$ is a square matrix with all elements on its main diagonal equal to $1$, and every row containing exactly two off-diagonal elements equal to $-1$; all other elements are equal to $0$. ...

**11**

votes

**2**answers

292 views

### Suggestion for framing a course in Representation theory + Spectral graph theory

I am going to give a course in spectral graph theory to graduate students. I want to learn and teach the connection between the spectral graph theory and the representation theory of finite groups. I ...

**1**

vote

**2**answers

142 views

### From one eigenvector to many, in a very local graph?

Let $\Gamma$ be an undirected graph of bounded degree $d$ with $V = \{1,2,\dotsc,N\}$ as its set of vertices, and edges only between vertices that are at a distance $\leq M$ apart (where $M$ is much ...

**25**

votes

**2**answers

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

**3**

votes

**0**answers

107 views

### Chromatic number of regular graphs using spectra

There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf's and Hoffmann's inequalities, which put together ...

**9**

votes

**2**answers

174 views

### Conjecture of van der Holst and Pendavingh related to bound for Colin de Verdière invariant

In their 2009 paper (“On a graph property generalizing planarity
and flatness”. In: Combinatorica 29.3 (May 2009), pp. 337–361. issn: 1439-6912.
doi: 10.1007/s00493-009-2219-6.), van der Holst and ...

**5**

votes

**0**answers

89 views

### Closed paths, closed trails and traces

Let $A$ be the adjacency matrix of a (non-oriented) graph $\Gamma$. Then $\textrm{Tr} A^k$ equals both the sum $\sum_i \lambda_i^k$ of $k$th powers of eigenvalues of $A$, on the one hand, and the ...

**0**

votes

**0**answers

76 views

### How to compute the sum of a product of eigenvalues, $\sum_{k=1}^n \lambda_k \lambda'_k$

$\DeclareMathOperator\Cay{Cay}$$G$ is an abelian group of order n. Let $\Gamma_1=\Cay(G,S_1)$ and $\Gamma_2=\Cay(G,S_2)$. (Here, $S$'s are symmetric subsets of $G$ such that $S=S^{-1}$ and $1\notin S$,...

**4**

votes

**1**answer

123 views

### Digraphs with unique walk of length $k$ between any two vertices

Let $G$ be a digraph such that there is an unique directed walk of length $k$ between any two vertices.
Equivalently, if $A$ is the adjacency matrix of $G$, then $A^k$ is the matrix with all entries $...

**1**

vote

**0**answers

44 views

### Cheeger constant of truncated hypercube

Look at the $d$-dimensional hypercube and truncate it. This means one replaces each vertex by a cycle (of length $d$) in such a way the the new graph is 3-regular.
Question 1: What is the asymptotic ...

**4**

votes

**1**answer

111 views

### Relation between Kirchhoff's Circuital law and Matrix tree Theorem

I'm not a professional mathematician, just an undergraduate student. I was reading Introduction to Graph Theory by West, I came over the topic which discuses the methods to find the spanning trees in ...

**4**

votes

**1**answer

165 views

### An eigenvalue upper bound for 1-walk-regular graphs

Let $G$ be a graph and suppose that $G$ is 1-walk-regular (or, if you prefer, vertex- and edge-transitive, or distance-regular).
Let $\theta_1>\theta_2>\cdots>\theta_m$ be the distinct ...

**2**

votes

**0**answers

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

**2**

votes

**1**answer

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

**5**

votes

**2**answers

337 views

### Fiedler vector, what else?

In the spectral analysis of a graph with 1 connected component, the first non-trivial eigenvector (corresponding to the non-zero smallest eigenvalue) is also called the Fiedler vector. This vector is ...

**4**

votes

**1**answer

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

**2**

votes

**0**answers

59 views

### Upper bound for smallest eigenvalue of infinite family of graphs

Let $\left\{G_{n}\right\}_{n=1}^{\infty}$ be a sequence of regular simple connected graphs with at least one edge such that $G_i$ is an induced sub-graph of $G_{i+1}$ and is not equal to $G_{i+1}$.
...

**1**

vote

**1**answer

123 views

### Cayley graphs on $Z_{11}$ and $Z_p$

I want to find all cayley graphs on $Z_{11}$. I know how many connected cayley graphs exist but i want to find all of them, connected or not, to find their eigenvalues. I found some of them and a ...