# 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
Filter by
Sorted by
Tagged with
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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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$...
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|)$...
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 ...
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 ...
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 ...
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
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 ...
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
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
182 views

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

### On cospectral graphs

Is there examples of non-isomorphic cospectral graphs having Non-isomorphic automorphism groups? Isomorphic automorphism groups?
1 vote
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
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 ...
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
78 views

45 views

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