Questions tagged [spectral-graph-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
25
votes
3answers
975 views

Reverse Graph Spectra Problem?

Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the Laplacian) eigenvalue decomposition (also called the spectra of a graph). But what ...
27
votes
2answers
756 views

Papers to credit for spectral partitioning of graphs

If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity $\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|...
8
votes
2answers
427 views

Spectral techniques for genus of a graph

A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.
24
votes
6answers
2k views

Introduction to spectral graph theory

What are the basic references? Are there any good, high-level surveys of SGT and its applications to CS in general and machine learning more specifically?

1
2