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
5 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
168 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
38 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
135 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
72 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
61 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
65 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
39 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
77 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
234 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
1 vote
0 answers
89 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
  • 501
3 votes
0 answers
64 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
107 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
44 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
207 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
51 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
118 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
33 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
105 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
303 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
115 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
31 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
62 views

On eigenvalues of signed complete graphs

From Akbari et al. -1 as well as Akbari et al. -2, we have that the eigenvalues of a signed complete graph $K_n$ with the negative edges forming an induced graph $H$ with order $k$ has the ...
vidyarthi's user avatar
  • 2,007
0 votes
0 answers
71 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
  • 3,898
2 votes
1 answer
122 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
  • 3,898
1 vote
1 answer
118 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
  • 3,898
6 votes
1 answer
387 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
  • 3,898
0 votes
1 answer
104 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
86 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
31 views

Relation between the left-dominant eigenvectors (eigenvector corresponding to 0 eigenvalue) of two Laplacian matrices

Let $G_1=(v,\epsilon_1)$,$G_2=(v,\epsilon_2)$ be two graphs with the same set of vertices and $\epsilon_1 \subset \epsilon_2$. $L_1$ and $L_2$ be the Laplacian matrices associated with graph $G_1$ and ...
SREEJEET MAITY's user avatar
0 votes
0 answers
122 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
182 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.2k
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.5k
5 votes
0 answers
177 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,143
0 votes
0 answers
52 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
306 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
381 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
123 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
122 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
191 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
269 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 vote
0 answers
171 views

Non-backtracking operator and spectra

Let $A$ be the adjacency operator of a symmetric graph $\Gamma$. (It may be weighted and/or non-regular, but, to keep it simple, let us say it is unweighted and regular of degree $d$.) We want to ...
H A Helfgott's user avatar
  • 19.3k
7 votes
0 answers
193 views

Surprising symmetry in the Ramanujan bound

The condition for a connected $(q+1)$-regular graph to be Ramanujan is that every nonzero eigenvalue $\lambda$ of the graph Laplacian satisfy $$q+1-2\sqrt{q}\le \lambda\le q+1+2\sqrt{q}.$$ With a ...
Antoine Labelle's user avatar
8 votes
0 answers
122 views

Conceptual explanation for the gap in the spectrum of biregular trees

Ramanujan graphs are defined as $(q+1)$-regular graphs for which all nontrivial eigenvalues of the adjacency operator are contained in the interval $$[-2\sqrt{q}, 2\sqrt{q}].$$ The reason for this ...
Antoine Labelle's user avatar
1 vote
0 answers
81 views

Graph energy and spectral radius

Suppose $G$ is a simple graph of order $n$ with eigenvalues $\lambda_1\geq \cdots\geq \lambda_n$. I've encountered the quantity $L=\big\vert |\lambda_1|-|\lambda_2|-\cdots-|\lambda_n|\big\vert$. Note ...
Angel's user avatar
  • 171
2 votes
1 answer
80 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 ...
Tardis's user avatar
  • 1,077
4 votes
0 answers
132 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 ...
baronbrixius's user avatar
1 vote
0 answers
60 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 ...
apg's user avatar
  • 612
0 votes
0 answers
111 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 ...
Tardis's user avatar
  • 1,077
0 votes
0 answers
52 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 ...
vidyarthi's user avatar
  • 2,007

1
2 3 4 5
8