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
0
votes
0answers
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. ...
0
votes
0answers
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 ...
2
votes
2answers
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 ...
3
votes
2answers
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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$, ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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$,
...
0
votes
0answers
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 ...
2
votes
1answer
40 views
Eigenvalues of complement of regular graphs
So I have encountered the following fact:
Let $G$ be a $d$-regular graph with adjacency eigenvalues $\lambda_1\geq...\geq\lambda_n$. Then its complement graph $\bar{G}$ has eigenvalues $n-1-\lambda_1,-...
1
vote
1answer
25 views
Are two distance regular graphs with the same intersection array also cospectral for their Laplacian matrices?
So we know that two DRGs with the same intersection array must be co-spectral on their adjacency matrices, i.e. their adjacency matrices have the same set of eigenvalues.
But is this necessarily true ...
1
vote
1answer
56 views
Graphs with large automorphism groups
While most graphs have trivial aut group (https://www.sciencedirect.com/science/article/pii/S0012365X08006900, https://users.renyi.hu/~p_erdos/1963-04.pdf, and also from sage simulations), I am ...
0
votes
0answers
23 views
Spectral gap of continuous-time Markov chain on nonnegative integers: The geometric long indel length chain
Let $S=\mathbb Z_{\ge0}$ be the nonnegative integers, and let $T=\mathbb R_{\ge0}$ be the nonnegative real numbers. Next, let $\gamma\in(0,1),r\in(0,1),$ and let $Q=(Q_{n,m})_{n,m\in S}$ be such that ...
0
votes
0answers
11 views
Laplacian spectrum of split graph
I want to know the Laplacian spectrum of split graph? It is known that complete split graph $CS(n,\alpha)$ is Laplacian integral. it will be of great help if anyone explain the Laplacian spectrum of ...
1
vote
1answer
62 views
Eigenvalue of block matrix with different size block
I was reading the paper "Consistency of spectral clustering in stochastic block models", by J.Lei and A.Rinaldo (arXiv link).
In the proof of Corollary 3.2, the author utilize an equality $\...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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? ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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$ (...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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$, ...
0
votes
0answers
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.
...
0
votes
0answers
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, ...
0
votes
0answers
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 ...
-1
votes
1answer
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?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
1answer
19 views
Solutions to generalized eigensystem
Is there a method to solve for $(\lambda, \vec{v})$ eigenpair in the following system?
$$L\vec{v} = \lambda M \vec{v}$$
Here $\lambda \in R$, $\vec{v} \in R^n$, $L \in R^{n \times n}$, and $M \in R^{...
1
vote
0answers
16 views
Adjacency spectra of a graph interpretation
I'm not a mathematician and I have a question about spectral graph theory.
Is it possible to conclude that we have a fully connected network, if an adjacency spectra of a graph is continuous with no ...
1
vote
1answer
88 views
Spectrum of the n-cycle graph $C_n$, $n\ge3$.
I am looking for the spectrum of a cycle graph i.e, eigenvalues of adjacency matrix of $C_n$ and their multiplicities.
I know that the adjacency matrix of $C_n$ is always a circulant matrix. Hence, ...
0
votes
0answers
21 views
Eigenspectra of graphs produced by joining a single edge
Lets say I have two graphs $G_1$ and $G_2$ which are defined on a disjoint set of vertices, $V(G_1)$ and $V(G_2)$, such that there is no edge connecting any $V(G_1)$ and $V(G_2)$. So basically I have ...
0
votes
1answer
46 views
How to compute the Perron vector
I'm new to spectral graph theory and I just read Laplacians and the Cheeger inequality
for directed graphs. In this paper, the author proposed transition probability matrix using Perron-Frobenius ...
0
votes
0answers
27 views
Divisibilty Graph and Eigenvector Centrality
The Divisibility Graph is constructed as follows. Let the vertex set V be the finite set of first n natural numbers {1,2, ...n}. Draw an edge between i and j if i divides j. This graph is an ...
1
vote
0answers
33 views
Upper bound of the energy of the graph
Let $\alpha_n \leq \alpha_{n-1} \leq \cdots \alpha_1$ be all eigenvalues of a graph $G$ (where the eigenvalues of $G$ is the eigenvalues of its adjacency matrix $A(G)$).
Let $n = |V(G)|$ be the ...
0
votes
2answers
74 views
Book recommendations for spectral graph theory
I am working on a Natural Sciences related project, which involves graph theory. I have calculated the Laplacian and Adjacency spectra of my graphs and now have to interpret it.
However, I am not a ...
1
vote
1answer
164 views
upper bound for the sum of absolute value of eigenvalues, the corresponding matrix is real symmetric with diagonal 0's
$A=\left(a_{ij}\right)\in M_{n\times n}(\mathbb R)$ s.t.
$a_{ij}=a_{ji}=\begin{cases}0,&i=j\\0\lor 1&i\ne j\end{cases}$
The eigenvalues of $A$ are $\lambda_1, \dots, \lambda_n$
I want to ...
0
votes
0answers
14 views
Are there any bounds on the decay rate of the spectrum of graph laplacians?
I am trying to analyze graph laplacians and in that context, I want to know about the spectral decay of graph laplacians i.e. how fast does the tail sum of its eigenvalues decays? Any research answers/...
3
votes
1answer
91 views
Relation of row sums to largest eigenvalue
I know that the largest eigenvalue of a graph is bounded between the minimal and maximal row sum of the matrix. If I have a $0-1$ symetric matrix (an adjacency matrix) and I know $k$ of the rows have ...
0
votes
0answers
17 views
Graph laplacian eigenvector distance metrics
I'm trying to study distance metrics between graphs which are permutation invariant for a research problem I am working on. So there is the eigenvalue distance which worked well for me, but I'm ...
0
votes
1answer
54 views
Geometric mutiplicity of 0 in laplacian graphs
I am reading lecture notes on Laplacian matrices of graphs
I don't understand why it should be true the following sentence, below Theorem 3.1.3, which is the famous theorem that links the dimension ...
1
vote
1answer
46 views
Cauchy-Binet formula proof confusion
I am doing a project for a graph theory course and would like to prove the Matrix Tree Theorem. This proof uses the Cauchy-Binet formula which I need to prove first. I have found many different proofs ...
0
votes
1answer
38 views
Estimating a sum of cosines related to random walk on $\mathbb{Z}_{n}^{n}$
I'm looking for help asymptotically estimating a sum. For positive integer $n$, let $[n]:=\{0,2,\dots,n-1\}.$ (I know it's nonstandard notation, but it makes the expressions easier to write.) Let $t=t(...
1
vote
0answers
82 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 ...
1
vote
1answer
100 views
Trying to understand relationship between Dirichlet energy of graphs and discrete laplacian
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$,
$$
\...
