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

483 questions
Filter by
Sorted by
Tagged with
11 views

### How to determined the Gutman index on linear hexagonal chain?

I want to determine Gutman index. We evaluated $d_id_jd_{ij}$ for all vertices (fixed $i$ and for all $j$) (there are three types of vertices) and then added all together and finally divided by two. ...
9 views

### Degree Matrix of Fully connected graph

https://www.kaggle.com/vipulgandhi/spectral-clustering-detailed-explanation In this blog post about spectral clustering it states that we can just use the Gaussian Kernel directly. "Generally we ...
41 views

### Which algebraic real numbers are eigenvalues of a finite graph?

Since the adjacency matrix of a finite graph has integer entries, its eigenvalues are algebraic. Since the adjacency matrix is also symmetric, the eigenvalues are all real. Can all algebraic real ...
73 views

### What does the value of eigenvectors of a graph Laplacian matrix mean?

I know that the eigenvectors of a Laplacian matrix of a graph are so important. They show the locality over the graph (as I know). But whatever I've read about an eigenvector of Laplacian graph is ...
22 views

### Can the Laplacian of two graphs have the same eigenvectors but different eigenvalues?

We know that the Laplacian matrix of a simple graph can be diagonalized as $L = U\Lambda U^T$ where $U$ shows eigenvectors and $\Lambda$ contains the eigenvalues. Can the Laplacian of two different ...
55 views

### Eigenvalues and eigenvectors of laplacian matrix of cycle graph

I'm interested in finding the eigenvalues and eigenvectors of the Laplacian matrix of a cycle graph with $n$ vertices (so - a 2-regular connected graph with $n$ vertices). The degree matrix is $D=2I$, ...
31 views

### Spectrum of a labelled complete graph $K_n$

Suppose, $K_n$ is a complete simple graph with each edge label $k$. Then its adjacency matrix $A(K_n)$ has all the entries zero along the diagonal, and each non-diagonal entries are $k$. What are ...
62 views

### Is there a way to count the number of vertices in a connected subgraph S that is part of a larger, disconnected graph G?

I apologize a head of time if this has been answered elsewhere. I have a random graph G, and this graph is disconnected and contains a unknown number of connected subgraphs (not all vertices in G's ...
51 views

### Eigenvalues of generalized Laplacian graph matrix

Consider a real matrix $A = [a_{ij}]_{1 \leq i,j \leq n} \in \mathbb{R}^{n \times n}$. If for any $i \neq j$, $a_{ij} \leq 0$, and for any $1 \leq i \leq n$, $a_{ii} = -\sum_{j\neq i} a_{ij} \geq 0$, ...
32 views

### Renormalization of a graph adjacency matrix

I know for graph adjacency matrix $A$ and degree matrix $D$, the eigenvalues of $I+D^{-1/2}AD^{-1/2}$ are in $[0,2]$ and repeated use of this as a filter will cause the numerical insatbility. I also ...
40 views

27 views

### Proof of distance-regular graphs being cospectral

I saw from the Wikipedia page for distance-regular graphs that: Two distance-regular graphs are cospectral if and only if they have the same intersection array. But I couldn't find any proof for this ...
6 views

### Spectral gap of cycle-like graph

Let $C_{n,2d}$ be a graph with vertex set $V=\{0,1,\dots n\}$, where $x$ is adjacent to $y$ if $x\neq y$ and there exists $-d \le k\le d$ such that $x \equiv y+k$ modulo $n$. Recall that the spectral ...
7 views

### What is the relationship between beta index and energy of a simple undirected graph?

The beta index (measure of connectivity) $\beta$ of a graph $G$ is defined as the ratio of the number of edges to the number of vertices of $G$. While, the energy of the adjacency matrix of the ...
41 views

### Number of strongly connected components of a digraph and the Laplacian

The multiplicity of the zero eigenvalue of the Laplacian matrix of an undirected graph is equal to the number of its connected components. I am wondering if a similar result holds for directed graphs? ...
22 views

### Existence of an equitable partition in a graph

I've been reading several articles about an equitable partition. I haven't seen any criterion to see if a graph has an equitable partition. All results I have seen so far are about starting with ...
23 views

### Unsure about Linearized Cluster Assignments via Spectral Ordering paper

I've been attempting to implement the method of linearized cluster assignments to cluster data just as shown in Linearized Cluster Assignment via Spectral Ordering by Chris Ding and Xiaofeng He. I've ...
44 views

### The notation of graph Fourier transform

In spectral graph theory, given $N \times N$ graph Laplacian matrix $L$ and the graph signal $f \in \mathbb R^N$ , the graph Fourier transform is defined as: $\hat{f}(l)=\langle u_l , f\rangle$ (...
46 views

### Why do the the Laplacian matrix or positive semidefinite matrix have n eigenvalues?

This proof conclusion is that the Laplacian matrix has n eigenvalues because it is a positive semidefinite matrix. I don't get why does it have n eigenvalues. Can someone please explain me this? By ...
36 views

### Can a regular graph have the same Laplacian spectrum with a non-regular one?

So the Laplacian matrix of an undirected graph $G$ is $L(G)=D(G)-A(G)$, where $D(G)$ is the diagonal degree matrix and $A(G)$ is the adjacency matrix, as usual. I can easily prove the case when the ...
11 views

### Graph Laplacian eigenvectors similarity measures?

I am working with undirected, weighted graphs. Lets say I have two graphs $\mathcal{G}_1$ and $\mathcal{G}_2$ with laplacians $L_1 = \Psi_1 \Lambda_1 \Psi_1^t$ and $L_2 = \Psi_2 \Lambda_2 \Psi_2^t$, ...
31 views

### What do commuting Laplacian matrices mean for their corresponding graphs?

Let us consider two undirected graphs $G$ and $H$. Their corresponding Laplacian matrices are $L_g$ and $L_h$, both symmetric and positive semi-definite. Neither of the graphs are fully connected. ...
33 views

### Laplacian and eigenvectors relationship

I have a Laplacian matrix $L_G$ of a connected and undirected graph $G$. $L_G$ is symmetric, positive semi-definite. I have another laplacian $L_H$, that is also symmetric and positive semi-definite, ...
44 views

### Product of a matrix and eigenvector

I am working on a problem. Given symmetric and positive semi-definite $n\times n$ matrix A, with real and non-negative and distinct eigenvalues $\lambda_i$, and $\lambda_1=0$ and corresponding ...
34 views

### Spectrum of Complete Graphs [closed]

What properties may be deduced from the spectrum of complete graphs such as number of edges or regularity?
45 views

### Beauty of Spectral Graph Theory

Why would one choose to study spectral graph theory? Where can the spectrum of complete graphs, for example, be applied in real- life example or of any graph in general? A brief historical background ...
17 views

### Given an eigenvalue of a tree, what about that eigenvalue when you remove a path from it?

Let $T$ be a tree and $\theta$ an eigenvalue of multiplicity m $\gt$ 1. Let $P$ be a path in $T$. Then prove that $\theta$ is eigenvalue of $T$ \ $P$ with multiplicity at least $m-1$. I tried ...
27 views

### Does the graph have better connectivity if it has larger second smallest eigenvalue of L?

I'm sorry if this question is quite primitive, but I am not a mathematician, who was thrown into a graph theory. It is stated that: "In spectral graph partition theory, the eigenvector ${𝑣_2}$ (also ...
19 views

### Mixing time of the random walk on $\mathbb{Z}_{2} \times \mathbb{Z}_{3} \times \cdots \times \mathbb{Z}_{n}$
For an integer $k \geq 2$, the simple random walk on the cycle $\mathbb{Z}_{k}$ proceeds by moving one step clockwise or counterclockwise, each with probability $1/2.$ I'm interested in the random ...
I'm a noob cs masters student trying to understand how the laplacian and the Dirichlet sum are related. So there is this popular expression with graph adjacency matrix $A$ and the laplacian $L$,  \...