# Questions tagged [spectral-graph-theory]

For questions related to the study of properties of a graph in relationship to the spectral properties of some associated matrix.

605 questions
Filter by
Sorted by
Tagged with
30 views

### What are the properties of the incidence matrcies of undirected graphs

Here is the definition of incidence matrix I find on Wikipedia https://www.wikiwand.com/en/Incidence_matrix Suppose we have a graph $G$ with $N$ nodes and $e$ edges (we only consider undirected graphs ...
• 1
35 views

### Proof of: Connected graph with three distinct adjacency matrix eigenvalues with the largest eigenvalue nonintegral is complete bipartite.

In the paper "Graphs with Three Eigenvalues" by E. R. van Dam, proposition 2 says that if a connected graph has three distinct eigenvalues and the largest is nonintegral, then it's a ...
• 21
20 views

### Constructing a graph with a given Fiedler vector

Given $\boldsymbol u \in \mathbb{S}^{n-1}$, how could one construct a (weighted, connected) graph whose Fiedler vector $\lambda_{2}(D-A)$ — that is, a unit-norm eigenvector corresponding to the second-...
• 21
27 views

### Number of Shortest Paths Through Any Edge on a Discrete Torus

I am currently stuck with the following problem: Consider the setting of a random walk on a discrete torus with $d$ dimensions and grid Size $L$. That means considering a simple (no loops or multiple ...
26 views

### Show that if $A(m, n)$ is nonsingular, then ${m + n \choose n}$ is even

The problem statement from Exercise 1(a) of chapter 6 of Algebraic Combinatorics by Richard Stanley: Let $A(m, n)$ be the adjacency matrix (over $\mathbb{R}$) of the Hasse diagram of $L(m, n)$, the ...
28 views

### Eigenvectors of Johnson Graph $J(N,2)$

I am having trouble finding an orthogonal basis of eigenvectors of the Johnson Graph $J(N,k)$ with k=2 in an explicit form. In the paper "On the reconstruction of eigenfunctions of Johnson graphs&...
1 vote
54 views

• 35
1 vote
79 views

### Why eigenspace of -1 orthogonal complement of 1?

Suppose eigenvector of $A(K_n)$ that is orthogonal to $1$ satisfies $A(K_n)v=-1v.$ Hence, $-1$ is an eigenvalue of $K_n$. The argument used to flush out $-1$ revealed also that the eigenspace of $-1$ ...
82 views

65 views

### What does mean bisection of graph?

I am struggling to understand bisection of graph. I searched in internet (less article available in the internet) I found this below paragraph: A bisection of a graph is a bipartition of its vertex ...
485 views

### What is canonical spectral theorem?

My teacher has given me the following definition of the canonical spectrum theorem: Let a matrix the $A \in M_{n\times n}(\mathbb{R})$, and set of eigenvalues, $\sigma(A)$={$\lambda_1$,$\lambda_2$........
30 views

• 553
47 views

• 332
1 vote
54 views

### On the smallest eigenvalue of the complement of a regular graph

While reading on graph theory and its applications, I came across a problem which stated if $\bar{G}$ is the complement of a regular graph then its eigenvalues are $-\lambda_i-1$ and $n-1-k$ where $G$ ...
• 124
1 vote
I'm currently reading this article (1) and I want to verify equation (4) and (5). I will reproduce the claim here. Let $P$ be a transition matrix and $\phi_0$ be the stationary distribution of $P$. ...
There is a polynomial time algorithm by Leighton and Miller for deciding whether cospectral graphs with eigenvalues of multiplicity $1$ are isomorphic. However, are there any known cospectral graphs ...