**6**

votes

**1**answer

359 views

### Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas.
In the following all graphs are simple and connected.
Let $G$ be graph with vertex set $V=\left\{v_1,v_2,\...

**3**

votes

**2**answers

381 views

### What is the state of the art on triangle-free strongly regular graphs?

From what I've read I've gathered the following facts:
There are seven known such graphs.
Certain parameter sets are ruled out by the Krein conditions and the absolute bound.
Beyond that, little or ...

**7**

votes

**1**answer

443 views

### How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...

**1**

vote

**2**answers

153 views

### Are trees spectrally determined?

Are trees (connected acyclic graphs) determinable up to isomorphism by their spectra or characteristic polynomials? If not, what other pieces of information may help determine the tree?

**3**

votes

**0**answers

304 views

### A problem on graph theory and complex numbers!

Let ${\mathcal G} = ({\mathcal V},{\mathcal E})$ be a simple connected undirected graph with $n$ vertices. Also let $z_1, \ldots, z_n \in {\mathbb C}$ be complex numbers such that
$$
||z_1||=\ldots = |...

**15**

votes

**4**answers

437 views

### Spectral theory of graph Laplacian besides $\lambda_2$

Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of ...

**3**

votes

**1**answer

302 views

### Graph Laplacian simple eigenvalues

Is there a class of graphs (besides the path graphs) for which we know that the Laplacian L = D - A (where D is the degree matrix and A is the adjacency matrix) has simple spectrum, i.e. all Laplacian ...

**7**

votes

**2**answers

446 views

### Small eigenvalues and spectral clustering

Let $L$ be the discrete Laplacian associated to an undirected graph. It is well-known that the spectral gap of $L$, i.e. the smallest nonzero eigenvalue, is a measure of how well connected the graph ...

**2**

votes

**0**answers

90 views

### Effect of removing a Hamiltonian cycle on the Laplacian spectrum

Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$).
Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$.
...

**1**

vote

**0**answers

142 views

### Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...

**4**

votes

**1**answer

270 views

### What is the largest possible operator norm of a sparse (0,1)-matrix?

Inspired by this question, I was wondering about the following problem:
Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does ...

**-1**

votes

**1**answer

299 views

### Upper bound on iterations count for power iteration algorithm

I'm stuck trying to get upper bound on iterations count for power iteration algroithm for finding first eigenvalue of adjacency matrix $A$ given tolerance value. I've tried to figure something out ...

**4**

votes

**0**answers

144 views

### Relaxation = absorption?

Let $A$ be a stochastic matrix, that is, the entries are non-negative and each row adds to $1$. Assume that it is primitive, that is, $A^n$ has only positive entries for sufficiently large $n$. We ...

**0**

votes

**1**answer

328 views

### Random walk on the hypercube

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just ...

**11**

votes

**1**answer

279 views

### Variant of an Expander graph: Probability that S random points cast a shadow/projection of size at most S/2 on each face of a cube.

Consider an integer cube of size $\sqrt{k} \times \sqrt{k} \times \sqrt{k}$, where $k$ is an asymptotically large perfect square number. Place k points in this cube at uniformly random locations, i.e.,...

**1**

vote

**1**answer

165 views

### Spectrum of composition of graphs( lexicographic product)

I was wondering how to relate the spectra of the composition of two graphs in term of the factors...someone can help me?

**5**

votes

**1**answer

714 views

### How many distinct eigenvalues does a random graph have?

It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one.
But what is known about the ...

**0**

votes

**0**answers

112 views

### Global solution for spectral clustering

I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...

**11**

votes

**0**answers

468 views

### Ramanujan Digraphs?

In Gowers' paper on quasirandom groups, he suggests a spectral theory of bipartite graphs employ the singular values of the bipartite adjacency matrix. Accordingly, singular values appear to be a ...

**4**

votes

**2**answers

726 views

### signing a strongly regular graph

Let $A$ be the adjacency matrix of a strongly regular graph. When is it possible to sign $A$ (i.e. replace some of the +1 entries by -1) so that the resulting matrix has exactly two eigenvalues?
I ...

**5**

votes

**1**answer

373 views

### Dimension of Specht Modules $S^\lambda$

In the study of representation theory of $S_n$, we know that the irreducible characters of $\chi_\lambda$ of $S_n$ are indexed by partitions $\lambda \vdash n$. There are several methods in ...

**2**

votes

**1**answer

1k views

### Eigenvalues of directed Laplacian matrix $L$ and $DL$, where $D$ is a diagonal matrix with positive entries

I have a weighted Laplacian matrix $L$ of a strongly connected directed graph and a diagonal matrix $D$ with positive entries. Since the graph is directed, $L$ is non-symmetric real. Further, since ...

**1**

vote

**2**answers

426 views

### How to identify bridge nodes between nearly connected graph components in partitioned adjacency matrices?

I have adjacency matrices which have nearly connected components. That is partitions with a dense number of edges between nodes in the same group and few edges acting as bridges between these groups. ...

**0**

votes

**1**answer

884 views

### Find edge weights that fit given node weights

Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...

**2**

votes

**1**answer

2k views

### Can the first non-zero eigenvalue of a Laplacian matrix with more than 1 zero valued eigenvalue be used to reorder an adjacency matrix?

I have a graph with multiple connected components, and its adjacency matrix. I form the Laplacian matrix (wiki Laplacian matrix), and from the 1K nodes there around ...

**5**

votes

**1**answer

1k views

### Connection between eigenvalues of matrix and its Laplacian.

Hello!
There are two definitions of graph spectrum:
1) Eigenvalues of adjacency matrix $A$.
2) Eigenvalues of Laplacian of adjacency matrix ($L$).
Different sources offer different properties based ...

**1**

vote

**1**answer

156 views

### The cliques of cospectral graphs

There are some facts that can be found by the spectrum of adjacency matrix of graph.For example, the number of edges and vertices, is bipartite or not, is complete multipartite or not and so on. Can ...

**0**

votes

**2**answers

554 views

### Confused about orbits

I am trying to apply the main theorem of this paper to a certain kind of graph and keep getting confused. The theorem uses $rank(Aut\Gamma)$ which is defined as "the number of $Aut \Gamma$ orbits on ...

**1**

vote

**1**answer

186 views

### The smallest eigenvalue from an equitable partitions

Suppose that $G$ is a connected graph with equitable partition $\pi$. Then the eigenvalues of the divisor multigraph $G / \pi$ are all eigenvalues of $G$. (Perhaps excluding some pathological cases) ...

**1**

vote

**0**answers

145 views

### Lower bound for the difference between the maximum eigenvalue of a graph with the one of the one-edge-deleted subgraph

I have proposed very recently a question in the following link concerning the title of the current question:
Difference of the maximum eigenvalue of a graph with the one of one-edge-deleted subgraph
...

**3**

votes

**2**answers

284 views

### are there pairs of combinatorial graphs that are both isospectral and have the same matroid?

Two graphs are isospectral if the combinatorial Laplacian on them has the same spectrum, equivalently, the adjacency matrix has the same the set of eigenvalues (including multiplicities). Two graphs ...

**3**

votes

**1**answer

602 views

### “Nice” eigenvectors for (square of) adjacency matrix of a bipartite graph?

Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix.
I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be ...

**1**

vote

**3**answers

549 views

### Characteristic polynomial of hypercube graph

This is probably well-known, but... Define the $n$-dimensional hypercube graph $H_n$ as having for vertices the integers between 0 and $2^n-1$, and edges between integers differing by a power of 2. ...

**1**

vote

**1**answer

398 views

### Is there a closed form for the characteristic polynomial of the graph cycle (of n edges and n summits) ?

Is there a closed form for the characteristic polynomial of the graph cycle (of $n$ edges and $n$ summits)?
I know it for the graph path (it is a Chebyschev polynomial), but I couldn't find a ...

**2**

votes

**2**answers

392 views

### Extreme Laplacian eigenvalues

For each undirected (and unweighted) graph $G$ we define the Laplacian matrix by $L(G) = D(G)-A(G)$, where $A(G)$ should denote the adjacency matrix and $D(G)$ the diagonal matrix, where $D(G)_{ii}$ ...

**6**

votes

**0**answers

213 views

### When can the Cheeger constant be well-approximated by ``Hamming balls''?

Given a graph G, the Cheeger constant is defined by
$$
\DeclareMathOperator{\Vol}{Vol}
h_G := \min_{S \subseteq V, \Vol S \leq (\Vol G)/2} \frac{|\partial S|}{\Vol S}.
$$
Here, $\Vol S$ is the sum of ...

**1**

vote

**1**answer

174 views

### a variation on the theory of equitable partitions for graphs

Assume you have a graph with an equitable partition with respect to cells $V_1,\ldots,V_n$. Accordingly, you can take the cellwise average value of a function on the node set - in other words, the ...

**3**

votes

**1**answer

320 views

### Eigenvectors of asymmetric graphs

Let $G$ be an asymmetric connected graph. Then is it always the case that at least one of the eigenvectors of its adjacency matrix $A$ consists entirely of distinct entries?
Thanks!

**1**

vote

**0**answers

99 views

### expansion with respect to p-norms for p other than 2

Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$.
Let $x \in {\...

**5**

votes

**2**answers

273 views

### Number of trees with the same matching number

Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.
I have been trying to compute the value of $\...

**3**

votes

**0**answers

121 views

### inverse M-matrix times mixed-sign vector

Recently a colleague and I came across this unusual phenomenon.
Take $M\in\mathbb{R}^{n\times n}$ a singular irreducible M-matrix, and $b\in\mathbb{R}^{n}$ such that the system $Mx=b$ is solvable (so,...

**6**

votes

**1**answer

482 views

### Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

This question is motivated by a talk I went to earlier today.
Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$.
Let $$\lambda_1\geq \lambda_2 \geq\dots \geq \...

**1**

vote

**1**answer

140 views

### In what probability does cospectra of Cayley graph imply isomorphism of the corresponding group

In what probability does cospectra of adjacent matrix of Cayley graph imply isomorphism of the corresponding group?
Further more,In what probability does cospectra of adjacent matrix imply isomorphism ...

**14**

votes

**1**answer

649 views

### Convexity of spectral radius of Markov operators, Random walks on non-amenable groups

Let $P_1,P_2$ denote stochastic transition matrices on a countable set $I$.
Consider $P_1,P_2$ as operators on $\ell^2(I)$ given by multiplication.
Question
Under which conditions can we show that ...

**1**

vote

**1**answer

349 views

### Simple Laplacian versus simple adjacency matrix eigenvalues

If the eigenvalues of the Laplacian matrix of a graph G are all simple, is it always the case that the eigenvalues of the adjacency matrix of G are all simple as well?
Thanks in advance!

**0**

votes

**0**answers

134 views

### A graph eigenvalue problem

This is motivated by a graph problem considered by me. For a directed graph $G$ on nodes ${1,\cdots,N}$, denote its graph Laplacian by $L$($l_{ij}=-1$ iff there is an directed edge $j\rightarrow i$ ...

**1**

vote

**1**answer

873 views

### equitable partitions

It is well known that if $\pi$ is an equitable partition of a graph, then the spectrum of the corresponding partition matrix is a subset of the spectrum of the graph's matrix (where the matrix can be ...

**4**

votes

**1**answer

303 views

### Graphs which are “distance-regular” with respect to a vertex (but not distance-regular)

A distance-regular graph (DRG) is, in essence, a graph $\Gamma$ of diameter $d$ for which there are integers $c_i, a_i, b_i, (0 \le i \le d)$ such that for all vertices $x$ of $\Gamma$ and for all ...

**2**

votes

**2**answers

673 views

### Positive semidefinite decomposition, Laplacian eigenvalues, and the oriented incidence matrix

Suppose $A\in\mathbb{C}^{n\times n}$ is Hermitian and positive semidefinite with some decomposition $A=BB^*$, where $B=(b_{ij})\in\mathbb{C}^{n\times m}$ (not necessarily the Cholesky decomposition). ...

**7**

votes

**1**answer

449 views

### Diophantine elements in SU(2)

Following notions from [1], call a set of elements $g_1, \dots, g_k \in G = SU(2)$ Diophantine if it satisfies the following property: there exists a constant $D$ such that for every word $W_m$ of ...