The spectral-graph-theory tag has no wiki summary.

**1**

vote

**0**answers

80 views

### Spectra of lifts?

Hi everyone, we know that the lifted(covering) graph inherits every eigenvalue of the base graph. Friedman called eigenvalues of base graph the "old eigenvalues" of its lift. My question is, what can ...

**1**

vote

**2**answers

248 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

322 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

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

**3**

votes

**1**answer

603 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

142 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

289 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

137 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

98 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

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

**2**

votes

**1**answer

365 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

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

**0**

votes

**1**answer

227 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

353 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}$ ...

**5**

votes

**0**answers

149 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

140 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

246 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

87 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

249 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

110 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

362 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

125 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

596 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

267 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

126 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

573 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

261 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

521 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

419 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

373 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

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

**8**

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

**3**

votes

**1**answer

182 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

475 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)$ ...

**4**

votes

**3**answers

257 views

### Operation on Isospectral graphs

Suppose $G$ and $H$ are two isospectral connected graphs. Can we say anything about isospectrality of graphs that obtain by binary operation between $G$ and $H$?
For example,in special case, is ...

**5**

votes

**2**answers

327 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

236 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

335 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

230 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

106 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

797 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

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

**1**

vote

**2**answers

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

**6**

votes

**3**answers

1k views

### Random bipartite graphs

Consider the following situation: I have a set $A$ of $n$ vertices and a set $B$ of $N = n^2$vertices. I consider the bipartite graph $(A, B)$ and put at random $M = n^{1 + \varepsilon}$ edges (or I ...

**7**

votes

**3**answers

544 views

### Eigenfunctions of random graphs

Consider a random $d$-regular graph on $n$ vertices. What can be said about its nontrivial (i.e. orthogonal to the constant) eigenfunctions? For example, I'm interested whether there are "nodal ...

**5**

votes

**1**answer

266 views

### Second eigenvalue of suspension of a graph

Suppose I have some $d$-regular graph $G$. Let $\lambda = \max\{\lambda_2(G), |\lambda_n(G)|\}$ be the second largest eigenvalue of the adjacency matrix of $G$. Now take $\tilde{G}$, the suspension of ...

**3**

votes

**2**answers

707 views

### Complex Eigenvalues of Directed Graphs

I have been computing eigenvalues of adjacency matrices for several directed (not necessarily strongly connected) graphs and one remarkable property seemed to hold (each graph that I have examined ...

**4**

votes

**3**answers

611 views

### Spectral radius of a proper subgraph

I came across a Chinese reference in the paper "On the spectral radius of trees with ﬁxed diameter" by Guo and Shao. The attribute the following to Q. Li, K.Q. Feng in: "On the largest eigenvalue of ...

**30**

votes

**5**answers

2k views

### Is the Laplacian on a manifold the limit of graph Laplacians?

Here's the sort of thing I have in mind. Let $M$ be a Riemannian manifold, compact if it helps, and let $\Delta_M$ be the Laplace-Beltrami operator. Choose a sequence of triangulations of $M$ so ...

**2**

votes

**4**answers

639 views

### Spectral gap for random bipartite regular graphs

For a graph $G$, let its Laplacian be $\Delta = I - D^{-1/2}AD^{-1/2}$, where $A$ is the adjacency matrix, $I$ is the identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm interested ...