Questions tagged [spectral-graph-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
25
votes
3answers
981 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 ...
6
votes
2answers
453 views

Terminology for sparse cuts in graphs

I have found some ambiguity in how the graph parameters edge-expansion, uniform sparsest cut and conductance are defined and denoted. My questions are: what are the definitions that best match the ...
11
votes
0answers
158 views

Generating a random graph with constraints on spectrum

Consider two sequences $u_1 \geq u_2 \geq ... \geq u_n$ and $l_1 \geq l_2 \geq ... \geq l_n$ with $u_i \geq l_i$ for every $i$. Let $\mathcal{G}(l_{1:n},u_{1:n})$ be all undirected unweighted simple ...