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

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 343
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 ...
user avatar
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 ...
user avatar
  • 466
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 ...
user avatar
  • 343
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 ...
user avatar
  • 1,611
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 ...
user avatar
  • 1,611
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 ...
user avatar
  • 631
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$...
user avatar
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|) $...
user avatar
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 ...
user avatar
  • 877
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 ...
user avatar
  • 139
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 12.8k
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,...
user avatar
  • 141
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^...
user avatar
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 ...
user avatar
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$. ...
user avatar
  • 16.7k
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?
user avatar
  • 75
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 ...
user avatar
  • 75
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 ...
user avatar
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) \...
user avatar
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,\...
user avatar
  • 375
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}.$$ (...
user avatar
  • 16.7k
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 ...
user avatar
  • 16.7k
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?
user avatar
  • 12.8k
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 ...
user avatar
  • 4,431
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 ...
user avatar
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$ ...
user avatar
  • 1,119
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 < \...
user avatar
  • 41
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 ...
user avatar
  • 10.8k
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 ...
user avatar
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 $ ...
user avatar
  • 203
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 $...
user avatar
  • 209
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}...
user avatar
  • 209
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 ...
user avatar
  • 16.7k
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 ...
user avatar
  • 16.7k
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 ...
user avatar
  • 9,471
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 ...
user avatar
  • 21.3k
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 4,431
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 ...
user avatar
  • 9,471
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 ...
user avatar
  • 86.8k
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”. ...
user avatar
  • 6,495
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. ...
user avatar
  • 205
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 ...
user avatar
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 ...
user avatar
  • 16.7k
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....
user avatar
  • 16.7k

1
2 3 4 5
7