Mathematics Stack Exchange
Mathematics Stack Exchange

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.

In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix.

An undirected graph has a symmetric adjacency matrix and therefore has real eigenvalues (the multiset of which is called the graph's spectrum) and a complete set of orthonormal eigenvectors.

While the adjacency matrix depends on the vertex labeling, its spectrum is graph invariant.

597 questions
13
votes
1 answer

Eigenstructure of discrete Laplacian on uniform grid

The discrete Laplacian of a graph is the matrix $L = D - A$ where $D$ is a diagonal matrix with $d_{ii}$ being the degree of $v_i$, and $A$ is the usual adjacency matrix. Is there anything known about the eigenstructure of the discrete Laplacian of…
Suresh Venkat
  • 1,312
3
votes
0 answers

ELI5: What is spectral graph theory?

I am aware that there is already a similar question here, but unfortunately I find the discussion there to be beyond my grasp. I am looking for an intuitive explanation of spectral graph theory, as well as some examples of its applications in…
M.Y. Babt
  • 155
2
votes
1 answer

For simple connected graphs, does either "adjacency-matrix cospectral" or "distance-matrix cospectral" imply the other?

Background Two graphs are said to be adjacency-cospectral (or more commonly just cospectral) if the spectra of their adjacency matrices is the same. Similarly, two graphs are distance-cospectral if the spectra of their distance matrices is the…
Ben Mares
  • 431
  • 2
  • 8
2
votes
0 answers

Modifying Heat Kernel Equation for Graphs

In spectral graph theory, I am aware that the following weight recurrence: $$ w_t(v_i) = \frac{1}{2}w_{t-1}(v_i)+\sum_{v_j \mid \exists e_{ij} }\frac{1}{2deg(v_i)} w_{t-1}(v_j) $$ Can be expressed in terms of eigen-vectors and eigenvalues of the…
Zach Hunter
  • 1,828
2
votes
0 answers

Spectral Clustering vs Robust PCA

I am given a weighted adjacency matrix where some of the entries are corrupted. My goal is to cluster it. I also do not know the number of clusters. I have looked for papers that talk about this problem and I have found these two methods Decompose…
Sri Kalyan Yarlagadda
  • 21
1
vote
0 answers

A directed version of strongly regular graphs

Strongly Regular Graphs (SRGs) can be defined as $k$-regular graphs with exactly two distinct eigenvalues different from $k.$ Define Strongly Regular Digraphs (SRDs) as $k$-regular digraphs with exactly two distinct eigenvalues different from $k.$…
Patrick Sole
  • 396
1
vote
0 answers

Change in spectrum of graph by adding pendant vertex

I am wondering the following. If we add a pendant vertex to a graph we are changing the spectrum. Eigenvalue interlacing tells us that the largest e-value of the new graph is at least as big as that of the old, and the smallest is at least as small,…
user387394
  • 594
1
vote
1 answer

Quotient matrix and interlacing

If $A$ is an adjacency matrix of the connected graph $G$ and $B_\pi$ is its quotient matrix corresponding to an equitable partition $\pi={C_1,C_2,...,C_m}$. Since this quotient matrix is diagonally similar to a symmetric matrix. So if we take any…
محمد عتیق طا ہر
  • 13
1
vote
0 answers

Intuition for eigenvectors and eigenvalues of the adjacency matrix

I have good intuition regarding the eigenvectors and eigenvalues for a matrix describing a transformation in a Hilbert space and those of correlation or covariance matrices. For Hilbert space transformations, the eigenvectors are the new unit…
Mr.WorshipMe
  • 381
1
vote
0 answers

Can a graph be recovered from its Bonacich centrality vector?

Let $A$ be the adjacency matrix of a directed graph with $n$ vertices and spectral radius $\lambda$. Let $I$ be the $n \times n$ identity matrix and let $e \in \mathbb{R}^n$ be the vector of 1's. For $\gamma<\lambda$, the matrix $I-\gamma A$ is…
gregc
  • 41
0
votes
1 answer

For which spectrum is the following result for?

I don't know if I am the only one that feels this, but damn Spectral Graph Theory needs some notation change... Maybe it is because I am not so experienced in the field yet, but man every time I read a result on eigenvalues I am not certain to what…
KXK
  • 146
0
votes
1 answer

Equitable partitions in the undirected graph

Let $G$ be an undirected simple graph with the adjacency matrix $A$. Let $P_{\pi}$ be the characteristic matrix for an equitable partition $\pi$, such that $A P_{\pi} = P_{\pi} B_{\pi}$, i.e., $B_{\pi}$ is the quotient matrix for the partition…
Anirban Banerjee
  • 1
0
votes
1 answer

what graph have exactly one positive eigenvalue

I know a Complete k-Partite Graph have exactly one positive eigenvalue. can I say a graph with a exactly one positive eigenvalue is Complete k-Partite Graph? and is the answer yes? how to proof it ?
Fatemeh
  • 97
0
votes
1 answer

Equitable partitions in the graph

Let $R^V$ be the real vector space of all functions from $V(G)$ to $R$ and $A(G)$ is the adjacency matrix, while $Q(G):=D(G)+A(G)$ is the signless laplacian matrix. A characteristics function of a subset $U\subset V$ is denoted by $e_U$. As it is…
محمد عتیق طا ہر
  • 13
0
votes
1 answer

Fiedler vector for weighted graphs

The second smallest eigenvalue of the Laplacian matrix of a (connected) graph is known as the algebraic connectivity of a graph and the corresponding eigenvectors are known as Fiedler vectors. I got the idea of monotonicity properties of Fiedler…
G_0_pi_i_e
  • 984