**11**

votes

**1**answer

277 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, ...

**1**

vote

**1**answer

152 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?

**4**

votes

**1**answer

676 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

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

**10**

votes

**0**answers

430 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

665 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

332 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

386 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

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

**0**

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

**4**

votes

**1**answer

953 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

153 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

486 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

174 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

138 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

256 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

565 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

522 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

353 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

389 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

196 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

159 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

305 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

97 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

266 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

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

**5**

votes

**1**answer

451 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

139 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

639 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

332 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

132 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

809 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

297 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

638 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

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

**2**

votes

**2**answers

450 views

### Decomposition of $K_{10}$ in copies of the Petersen graph

It is a well-known and cute exercise in algebraic graph theory to show that $K_{10}$ cannot be written as the edge-disjoint union of three copies of the Petersen graph $P$. Indeed, the graph $G$ whose ...

**2**

votes

**2**answers

373 views

### Isoperimetric dimension of Graphs.

According to the wikipedia page on "Isoperimetric dimension", the isoperimetric dimension is invariant under quasi-isometries, even between manifolds and graphs:
"[...] the isoperimetric dimension is ...

**11**

votes

**0**answers

1k views

### A new lower bound for the chromatic number of a graph?

Let $S_{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph $G$. Let $S_{-}(G)$ denote the sum of the squares of the negative eigenvalues and $q$ the ...

**3**

votes

**1**answer

186 views

### Estimation of DS graph growth

We know that $DS$ graphs are such connected graphs that determinable by their adjacency spectrum.
Suppose $DS(n)$ and $G(n)$ show the number of $DS$ graphs and all graphs with $n$ ...

**2**

votes

**3**answers

517 views

### Non-isomorphic graphs with the same numbers of closed walks

Can somebody help me to construct two family of finite simple connected graph $G_i$ and $H_i$, $i=1, 2, \cdots,n$ ($n$ possibly large), such that:
$1)$ $G_i\ncong H_i$ for $i=1, 2, \cdots, n$
$2)$ ...

**5**

votes

**3**answers

299 views

### Operation on Isospectral graphs

Suppose $G$ and $H$ are two isospectral connected graphs. Can we say anything about isospectrality of graphs that are obtained by applying a binary operation to $G$ and $H$?
For example, to take one ...

**7**

votes

**2**answers

391 views

### cospectral graphs

The simple connected graph $G$ has $n$ vertices and we have:
1) $|E(G)|\geq \frac{n(n-1)}{3}$
2) we have the spectrum and degree sequence of $G$
3) $Spectrum(G)=Spectrum(H)$
Is $G \cong H$?

**1**

vote

**1**answer

265 views

### spectrum and degree sequence

We have the spectrum and the degree sequence of one graph.
Can we uniquely determine the graph with these given information?

**1**

vote

**2**answers

359 views

### Lovasz theta function of circulant graphs

Let $G$ be a cirulant graph with no loops at vertices and vertex degree $d$. Is the Lovasz theta function of this graph given by:
$\vartheta(G) = \max_{i}\frac{-N\epsilon_{i}}{-\epsilon_{i}+d-1}$?
...

**0**

votes

**1**answer

254 views

### Lovasz theta function - uses

Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?

**0**

votes

**1**answer

107 views

### Counting walks on proper colorings of odd cycles

Let $G$ be an undirected odd cycle. Let $f$ be a proper 3-coloring of $G$. If $w=v_1v_2...v_k$ is a walk on $k$ vertices of $G$, let $f(w)=f(v_1)f(v_2)...f(v_k)$. Let $W_k=\{f(w)|w$ is a walk on ...

**15**

votes

**2**answers

841 views

### Groups with a rational generating function for the word problem

This question comes more from curiosity than a specific research problem. Let G be a group and S a finite symmetric generating set. By the WP(G,S) I mean the set of all words in the free monoid on S ...

**5**

votes

**3**answers

465 views

### Bounds on maximal eigenvalue of a k-regular graph

Given a k-regular graph $G$ (every vertex is of degree k), one defines its Laplace operator as
$L(G)=D-A=kI-A$, where $I$ is identity matrix and $A$ adjacency matrix of $G$.
Let $\lambda_{1}\leq ...

**2**

votes

**2**answers

638 views

### Effect of different graph operations on spectrum of graph laplacian?

The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. The magnitude of this ...