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

529 questions
Filter by
Sorted by
Tagged with
1 vote
15 views

### Spectral radius and maximum degree of a graph [duplicate]

How can I show that the spectral radius of a graph $G$ is less than or equal to its maximum degree? I have an unweighted graph $G=(V,E)$, where $V$ is its vertex set and $E$ its edge set. The degree ...
10 views

### Graph Laplacian for weight matrix with negative edges

How can I normalize my weight matrix to get a positive semi-definite Laplacian, if I am using a weight matrix with negative edges?
26 views

### Eigenvalues of graph laplacian question

I need some guidance on solving the following question I am stuck on: Let L be a graph Laplacian matrix of a graph G = (V, E) with n vertices. Denote the eigenpairs of L by {λi,ψi} for every i=1..n, ...
17 views

### Can any Markov chain on a finite state space be modelled as a random walk on a graph? What about models of non-finite state space MC?

I am reading about mixing times of Markov chains, and one result I am looking at concerns characterising when a phenomenon called 'cutoff' occurs, based on "the inverse spectral gap of the Markov ...
1 vote
16 views

### Why Spectral Embedding leads us to the low-dimensional embeddings?

Dimension Reduction is well versed technique in Machine Learning. We often use this tool. One such tool is Spectral Embedding. It follows three steps:- Constructing the Adjacency Graph Choosing the ...
9 views

### How can I select K value of K-means from eigengap?

I have studied perturbation theory and spectral graph theory to calculate the optimal number of clusters .Eigengap heuristic suggests the number of clusters k is usually given by the value of k that ...
16 views

### Confusion regarding the derivation of graph convolution

I am currently studying Spectral Graph Convolutions, and I am following this document: https://atcold.github.io/pytorch-Deep-Learning/en/week13/13-1/. They have derived the convolution as follows: The ...
8 views

### Graph join and the Laplacian spectrum of a graph $G$ having eigenvalue 1 of multiplicity 2.

Let $G$ be a connected graph of order $n$ with a Laplacian spectrum of the following form $$\sigma_L(G)=\{0,1,1,\mu_4,\ldots,\mu_n\},$$ where all the eigenvalues are integer numbers with exactly one ...
69 views

### what are the benefits of using Spectral K-means over Simple K-means ? and how Spectral K-means overcomes the local minimum problem of K-means?

I have understood why K-means get stuck in local minima Now I am curious to know how spectral k-means helps to avoid this local minima problem? According to this paper A tutorial on Spectral, ...
20 views

### maximum eigenvalue of graphs different in only one edge

Show that if the graphs $G, G'$ differ in only one edge, then $|\lambda_1(G) − \lambda_1(G')|\leq 1$, where $\lambda_1$ indicates the maximum eigenvalue of a graph. First, I'm not sure if I ...
23 views

### Spectra of a weighted path graph

In Spectra of Simple Graphs , it is given that an unweighted path graph with $n$ vertices has eigenvalues $$2\cos(\pi j/(n+1)), j = 1,\cdots, n.$$ All multiplicities are 1. Assuming the edges of ...
5 views

1 vote
53 views

### prove that $\Delta(G)\leq \lambda_{max}^2$

Let $G$ be a graph and let $\lambda$ be its largest eigenvalue. Prove that $$\Delta(G)\leq \lambda^2$$ where $\Delta(G)$ is the maximum degree of vertices of $G$. I've seen this problem being regarded ...
105 views

### Meaning of eigenvalues of an adjacency matrix

I know the eigen vector of a matrix transformation is the vector that turns it into a scalar transformation. But in the context of a adjacency matrix and in a graph, what does the eigen vector or ...
15 views

### How RatioCut leads to unnormalized spectral clustering?

I have understood the underlying concepts of spectral clustering and how inter cluster distance equation is mapped to a matrix form and how it is optimized using lagrange multiplier. But unable to ...
20 views

1 vote
126 views

### Eigenvalues of the join of two graphs?

We define the join of two graphs $G = (V(G),E(G))$, $H=(V(H),E(H))$ as the graph: $$G \wedge H : = (V(G) \cup V(H), E(G) \cup E(V) \cup \{gh: g \in V(G), h \in V(H))$$ If I know the spectrum of the ...
1 vote
29 views

I want to prove $K_{n,n+1}$ is determined by the adjacency spectra, called DS graphs. I try to use theorem 1 of Esser and Harary. I suppose $tK_1+K_{p,q}$, $p\leq q$, has the same spectra with $K_{n,n+... 1 vote 1 answer 48 views ### why there is no graph whose largest eigenvalue,$\lambda_1$, lies in the intervals$(0,1)$or$(1,\sqrt{2})$? why there is no graph whose largest eigenvalue,$\lambda_1$, lies in the intervals$(0,1)$or$(1,\sqrt{2})$? I think it's becaues of if a graph doesn't have any edge then$\lambda_1=0$, if it has ... 1 vote 0 answers 40 views ### Normalize an adjacency matrix twice I am working on a graph clustering problem and i've seen that applying two consecutive normalizations on the adjacency matrix gives much better performance than when applying a single one. I first ... 3 votes 0 answers 37 views ### Trees with two eigenvalues? Is it possible for a tree of order$n$($n$even) to have eigenvalues$(\lambda_1, \ldots, \lambda_1, -\lambda_1, \ldots, -\lambda_1)$? Or perhaps$(\lambda_1, \ldots, \lambda_1, 0,-\lambda_1, \ldots,...
The generalised problem is as follows: Is there a condition on a symmetric positive-semi-definite matrix $A$ that ensures that it has a positive eigenvector, i.e. an eigenvector $Av = \lambda v$ such ...