**8**

votes

**3**answers

415 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 ...

**7**

votes

**2**answers

721 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 - ...

**8**

votes

**1**answer

695 views

### When the Lovász theta-function saturates its upper bound

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, ...

**2**

votes

**4**answers

857 views

### On the spectrum of random regular graph

For a random $d$-regular graph, where $d$ can be fixed or can grow slowly with the size of the graph $n$, what can we say about its spectrum - Do you believe it has simple spectrum?
Thank you,