Skip to main content

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
0 votes
0 answers
57 views

Second largest eigenvalue of graph

Let $G$ be a connected $d$-regular n-vertex graph and let $k:= k(n)\in \mathbb{N}.$ Given a Non-empty set of vertices $\phi\neq B\subseteq V(G),$ how can I prove that all but at most $\frac{\lambda_2|...
HDD's user avatar
  • 177
0 votes
1 answer
109 views

Function of eigenvalues of Laplacian matrix

Let $G$ be a simple $n$-vertex graph and let $\mu_n\geq\mu_{n-1}\geq\dots\geq\mu_1$ be the eigenvalues of its Laplacian matrix, how can I find a function $$f(\mu_1,\mu_2,\dots\mu_n) \text{ such that } ...
HDD's user avatar
  • 177
3 votes
0 answers
79 views

Inverse of adjacency matrix of overlapping cycle graphs?

Consider a graph composed of two overlapping cycles: one cycle of length $\ell$ and one cycle of length $m$ where the two cycles share $e$ edges. See picture as an example: The eigenvalues and ...
papad's user avatar
  • 272
0 votes
1 answer
98 views

Spectral theory: a key to unlocking efficient insights in network datasets

In the context of directed or undirected graphs, matrices such as adjacency and Laplacian matrices are commonly used. The eigenbasis of these matrices addresses some practical implications, such as ...
ABB's user avatar
  • 4,010
0 votes
0 answers
50 views

triangle free cubic graphs

Is there any classification of cubic triangle-free graphs? Which structural properties of cubic triangle-free graphs are known? How about their eigenvalues or any other useful properties?
user53093's user avatar
  • 105
2 votes
0 answers
81 views

A reference for high girth expander graphs

I'm looking for a reference to the existence of family of constant (or bounded by constant) degree graphs which are both high-girth (meaning the ratio girth/diameter is uniformly bounded from below by ...
Manor Mendel's user avatar
7 votes
3 answers
549 views

Real-world examples of unweighted directed graphs

Social Networks, Internet Traffic, Citation Networks, Transportation Networks, and Biological Networks exemplify real-world instances of unweighted directed graphs. Within these domains, the Graph ...
ABB's user avatar
  • 4,010
0 votes
0 answers
29 views

A class of directed graph, when their minimal polynomial of the adjacency matrix matches the characteristic polynomial

We consider an unweighted directed simple graph, $G$, with a Hamiltonian cycle. Q. Assume that the adjacency matrix of $G$ is non-singular. Do the characteristic and minimal polynomials of the ...
ABB's user avatar
  • 4,010
1 vote
2 answers
185 views

Topology of directed graph $G$ with non-singular adjacency matrix

Given a directed graph $G$ with non-singular adjacency matrix, Q. Is there a directed subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...
ABB's user avatar
  • 4,010
0 votes
0 answers
38 views

How can I measure similarity between two graphs with identical topology but different edge weights

I have two graphs, G1 and G2, with exactly the same topology. Their only difference lies in the edge weights, which vary between 0 and 1. How can I measure the similarity between G1 and G2 under these ...
k99's user avatar
  • 1
2 votes
1 answer
87 views

Testing for equal characteristic polynomials using a single determinant calculation

Let $A_1,A_2$ be $n\times n$ symmetric matrices over $\{0,1\}$, and let $p_1, p_2$ be their respective characteristic polynomials over the rationals. If $p_1 \ne p_2$, then there is some positive ...
Brendan McKay's user avatar
0 votes
0 answers
17 views

Bound the $\infty$-norm of the eigenvector of the second minimum eigenvalue of normalized Laplacian from below

I meet the above problem while reading a paper. The problem can be stated as below. Consider an undirected graph $G$. Let $\mathbf{v}$ be a vector such that $\mathbf{D}^{1/2}\mathbf{v}$ is the ...
Lasting Howling's user avatar
3 votes
1 answer
207 views

Some questions about induced subgraphs of the directed hypercube graph

Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
Agile_Eagle's user avatar
2 votes
0 answers
72 views

Given a low-rank symmetric positive semidefinite matrix and a basis of its nullspace, is there a fast way to get the nonzero eigenvalues?

I have a (possibly dense) $k\times k$ real matrix $L = AA^T + B^T B$, a type of combinatorial Laplacian (self-adjoint, symmetric, positive semidefinite) of rank $(k-n)$ and possibly repeated nonzero ...
BenJones's user avatar
2 votes
1 answer
136 views

Invertibility of message passing with invertible parametrization

Consider the message passing framework defined by, $$f(\boldsymbol{x}_i)= \boldsymbol{x}_i + \sum_{j \neq i} (\boldsymbol{x}_i -\boldsymbol{x}_j) g(\|\boldsymbol{x}_i -\boldsymbol{x}_j\|^2),$$ for $i=...
PonderingPolynomial's user avatar
2 votes
0 answers
84 views

Bound on the magnitude of the entries of the Laplacian pseudo-inverse

Let $L$ be the laplacian matrix of a connected graph $G$ with real positive weights and $N$ vertices, or that can be assumed to have binary weights for simplicity.My goal is to bound $\Vert L^+\Vert_{\...
sd24's user avatar
  • 21
3 votes
0 answers
67 views

Second eigenvalue of primitive matrix

Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$. The ...
Curious's user avatar
  • 143
0 votes
1 answer
73 views

Number of bi-directional (or symmetric edges) [closed]

I am trying to figure out the least number of directed edges that would be bi-directional after constructing a graph with $2k-1$ nodes that are each $k$ in-degree. For example, $2(2)-1=3$ nodes that ...
James's user avatar
  • 1
2 votes
0 answers
46 views

Regularize a graph while embedding the spectrum of adjacency matrix

Given an irregular graph $G$ whose maximum degree is $d$, I am interested in producing a new graph $G'$ which is regular and has the spectrum of the adjacency spectrum of $G$ embedded in the spectrum ...
Chaithanya's user avatar
1 vote
0 answers
81 views

Diameters of random bipartite graphs

Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
Zijian Wang's user avatar
2 votes
1 answer
253 views

Do balls in expander graphs have small expansion?

Consider a $d$-regular infinite transitive expander graph $G$, and let $B_r$ be a ball of radius $r$ in $G$. Can one place any upper bounds on the expansion of $B_r$? My intuition is that $B_r$ will ...
user3521569's user avatar
2 votes
0 answers
138 views

Max-cut from Laplacian

(This question seems like very standard material for those well-versed in the subject. I thought I would get a quick answer from Math stackexchange, but to no avail.) Given a weighted graph with $n$ ...
Thomas's user avatar
  • 511
3 votes
0 answers
71 views

Clique number and spectrum of a graph

In the Wikipedia article on Grassmann graph it is stated that in this graph: $$\omega=1-\frac{\lambda_{max}}{\lambda_{min}}$$ where $\omega$ is the clique number of the graph, and $\lambda_{max}$ and $...
Ghodrati's user avatar
  • 175
0 votes
1 answer
139 views

Spectral characterization of complete or complete bipartite graphs

The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs: Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
YuiTo Cheng's user avatar
1 vote
0 answers
45 views

Bounds on the spectral radius of a perturbed directed graph

Suppose $(G_n)$ is a sequence of strongly connected directed graphs (without multiple edges) with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be ...
a person's user avatar
8 votes
1 answer
224 views

Is there a bipartite graph with $\sqrt{2}$ as an eigenvalue with high multiplicity, specifically more than in the Heawood graph?

The Heawood graph is a $3$-regular graph on $14$ vertices. Its (adjacency) spectrum is $\{ (3)^1, (\sqrt{2})^6, (-\sqrt{2})^6, (-3)^1 \}$. So, $3/7 \approx 42.8\%$ of its eigenvalues equal $\sqrt{2}$. ...
The Amplitwist's user avatar
1 vote
0 answers
52 views

Controlling quantity related to Laplacian pseudo-inverse of Erdős–Rényi graph

Consider an $n$-node undirected graph $G = (V, E)$ equipped with weights $W$. Let $L$ be the weighted graph Laplacian matrix, i.e. $L_{ij} = -W_{(i,j)}$ for $(i,j)\in E$ and $L_{ii} = \sum_{j:(i,j)\in ...
yy98's user avatar
  • 11
2 votes
0 answers
124 views

Graph Laplacians, Riemannian manifolds, and object collisions

To preface this question, I am a part-time game developer and full-time optimization fiend. I am working on object collisions at the moment and many resources I have found online are more-or-less just ...
HeyoItsMateo's user avatar
1 vote
0 answers
38 views

Tightness of the bounding the operator norm of graph by average degree from below

Let $G = (V,E)$ be a simple graph with adjacency matrix $A$. It is well known that the largest eigenvalue $\lambda_{1}$ of $A$ is contained within the interval $[d, D]$ where $d$ is the average degree ...
user135520's user avatar
3 votes
1 answer
114 views

Spectrum of the adjacency matrix of certain directed graphs

For an undirected graph $G$, its adjacency matrix $A_G$ is symmetric, and by the (consequence of) spectral theorem, each of its Jordan blocks has size $1$. This is not true for a general directed ...
F J's user avatar
  • 161
7 votes
1 answer
333 views

Diameter bound for graphs: spectral and random walk versions

This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and ...
Stefan Steinerberger's user avatar
5 votes
0 answers
117 views

The Smith decomposition of the graph Laplacian and Locality

Let $X$ be a graph. Let $V(X)$ and $E(X)$ be the sets of vertices and edges of the graph respectively. If $f:V(X) \rightarrow G$ where $G$ is an abelian group, then one can define a graph Laplacian as ...
nabil's user avatar
  • 51
0 votes
0 answers
34 views

Resolvent estimates for Laplacians on directed graphs

Let us consider a directed and weighted graph $G$ with $N = |G|$ nodes. Denote the corresponding (weighted) adjacency matrix by $W \in \mathbb{R}^{N\times N}_{\geq 0}$ and let $D$ be the diagonal in-...
Qualearn's user avatar
0 votes
0 answers
80 views

When is the sum of matrices (circulant + [super upper triangular]) not diagonalizable?

By the circulant matrix $C \in M_n(\mathbb{R})$, we mean that $$ C = \left[\begin{array}{c|c|c|c} e_n & e_1 & \cdots & e_{n-1} \end{array}\right] $$ where $e_1,\dots,e_n$ are the standard ...
ABB's user avatar
  • 4,010
2 votes
1 answer
131 views

Is the sum of the circulant matrix with a super upper triangular matrix diagonalizable?

By the circulant matrix $C$ in $M_n(\mathbb{R})$, we mean that $$C=[e_n|e_1|\cdots|e_{n-1}]$$ where $e_1,\cdots,e_n$ are the standard basis vectors in $\mathbb{R}^n$. It is well-known that $$C=\...
ABB's user avatar
  • 4,010
1 vote
1 answer
166 views

Directed graph whose adjacency matrix admits only 0 as eigenvalue

Let $G$ be a directed graph and let $P_i$ be its vertices. Let $A$ be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$ if and only if there is a directed edge from $P_i$ to $P_j$, ($a_{i,...
ABB's user avatar
  • 4,010
6 votes
1 answer
437 views

Non-diagonalizability of the adjacency matrix of a directed graph

Let $G$ be a directed graph with no multiple edges or loops and let $P_i$ be its vertices. Let $A$ be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$ if and only if there is a directed ...
ABB's user avatar
  • 4,010
0 votes
1 answer
108 views

Two fractionally isomorphic graphs but only one having eigenvalue zero

I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) with adjacency matrices $A_G$ and $A_H$, respectively, such that $G$ and $H$ are ...
Sirolf's user avatar
  • 493
4 votes
1 answer
89 views

Strongly/distance regular graphs over $\mathbb{Z}_2^n$ with the same parameters

I am wondering if there is a known example of a pair of non-isomorphic graphs $G$ and $H$ that are both Cayley graphs for $\mathbb{Z}_2^n$ (for some $n$) and are both distance regular and have the ...
David Roberson's user avatar
0 votes
0 answers
123 views

On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph

Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...
shahulhameed's user avatar
5 votes
2 answers
191 views

Can we calculate the spectral radius of the universal cover for specific graphs?

Background For a finite graph $G$, let $\tilde{G}$ denote the universal cover of $G$. For a vertex $v$, let $p_{2n}(v)$ denote the number of paths of length $2n$ that start and end at $v$. The ...
Eric Naslund's user avatar
  • 11.3k
1 vote
0 answers
58 views

What do you call this class of matrices with a unique positive eigenvalue associated to a graph?

I am looking for the name of a class of symmetric matrices $M\in\Bbb R^{n\times n}$ that I can associate to a (finite simple) graph $G=(V,E)$ with $V=\{1,...,n\}$ and that have the following ...
M. Winter's user avatar
  • 12.8k
5 votes
0 answers
190 views

(How) does the spectral gap of the $n\times n$ Rubik's cube close with $n$?

Consider the spectrum of the adjacency matrix $A$ of the Cayley graph of the standard, 3x3x3 Rubik's cube generated with the usual quarter-turn and half-turn twists of each face (the Singmaster ...
Mark S's user avatar
  • 2,133
0 votes
0 answers
53 views

Comparing spectral radius of two graphs using the entry of Perron vector

Suppose we have a graph $G$. Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector. Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$. We ...
User8976's user avatar
  • 199
8 votes
0 answers
355 views

Explicit constructions of Ramanujan graphs

I am trying to find a list of all the explicit constructions of Ramanujan graphs. By a Ramanujan graph I mean a $k$-regular multi-graph $G$ such that all the non-trivial eigenvalues $\lambda$ of the ...
richarddedekind's user avatar
1 vote
1 answer
468 views

Vertex degree on random graphs

Let $p = d/n$ with $d$ constant. How do I prove that, with high probability, $G_{n,p}$ contains a vertex of degree at least $(\log n)^{1/2}$, where $G_{n,p}$ is a graph with $n$ vertices and the ...
Nir Kfir's user avatar
1 vote
1 answer
126 views

Eigenvalues of directed graph with one outward edge for each vertex

I am concerned with unweighted directed graphs where each node contains exactly one edge pointing to another node, which could be itself. In other words, each row of the adjacency matrix contains one ...
user3433489's user avatar
0 votes
1 answer
134 views

Entropy of eigenvectors of (traceless) laplacian of a bipartite graph

This problem is motivated by the edge states that sometimes appear (and sometimes not) at the level of Huckel hamiltonians for $\pi$-conjugated benzenoid hydrocarbons. If this sentence is cryptic, ...
Qwertuy's user avatar
  • 251
0 votes
1 answer
195 views

Series analyzed in Lubotzky–Phillips–Sarnak "Ramanujan Graphs"

In the LPS paper "Ramanujan graphs" the adjacency matrix of $X^{p,q}$, for simplicity say that $p,q\equiv1\mod{4}$ and $\left(\frac{p}{q}\right)=1$ (so, nonbipartite) and $n=\lvert X^{p,q}\...
zjs's user avatar
  • 465
3 votes
1 answer
297 views

Relation between spectra of a Cayley graph of a group and irreducible characters of that group

I know the following fact: If $G$ is an abelian group and $S\subset G$ be a subset of G such that $1\notin G$ and $S=S^{-1}$ and we draw an edge between $g$ and $h$ if and only if $hg^{-1}\in S$,then ...
Soumyadip Sarkar's user avatar

1
2 3 4 5
9