The tag has no wiki summary.

learn more… | top users | synonyms

15
votes
8answers
4k views

The first eigenvalue of a graph - what does it reflect?

A big-picture question: what "physical properties" of a graph, and in particular of a bipartite graph, are encoded by its largest eigenvalue? If $U$ and $V$ are the partite sets of the graph, with the ...
1
vote
1answer
184 views

PR[$\lambda_2 > x$] in $G_{np}$ model

Hi! Does anyone know of any statement relating the probability that the second largest eigenvalue of a random graph is bigger than $x$ to the parameter $p$ in the $G_{np}$ model?
6
votes
3answers
561 views

Generalization or Improvement of Cheeger inequality on Graphs

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. Let $A$ denote the adjacency matrix of $G$ and $D$ denote the diagonal matrix such that $D_{i,i}$ equals to the degree $d_i$ ...
8
votes
3answers
380 views

Classes of graphs for which isospectrum implies isomorphism ?

The spectrum of a graph is the (multi)set of eigenvalues of its adjacency matrix (or Laplacian, depending on what you're interested in). In general, two non-isomorphic graphs might have the same ...
6
votes
2answers
681 views

Spectrum of the Laplacian on G(n, p) and G(n, M)

A random graph in $G(n, p)$ model is a graph on $n$ vertices in which for each of the $n\choose{2}$ edges we independently flip a coin, then take the edge with probability $p$ or remove it with $1 - ...