# 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

402 questions
Filter by
Sorted by
Tagged with
57 views

• 4,010
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 ...
• 4,010
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 ...
• 493
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 ...
• 2,309
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$ ...
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 ...
• 11.3k
1 vote
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 ...
• 12.8k
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 ...
• 2,133
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 ...
• 199
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 ...
1 vote
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 ...
• 21
1 vote
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 ...
• 283
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, ...