Basics of spectral graph theory

I’ve given a short lecture on spectral graph theory in the Physical Applied Math group meeting. My notes are available as PDF.

The annotated reading list is below. I have copies of all the books listed so come and talk to me if you’re interested.

  1. An example of a common use of graph Laplacians as a stand-in for combinatorial optimization:
    Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.
  2. On structure of eigenvectors:
    Biyikouglu, T., Leydold, J., & Stadler, P. F. (2007). Laplacian eigenvectors of graphs (Vol. 1915). Berlin: Springer.
  3. THE monograph on spectral graph theory, a lot of material, but very readable.
    Chung, F. R. K. (1997). Spectral graph theory (Vol. 92). Published for the Conference Board of the Mathematical Sciences, Washington, DC. Sample chapters on Fan Chung’s page.
  4. The random walk picture:
    Lovász, L. (1996). Random walks on graphs: a survey. In Combinatorics, Paul Erdős is eighty, Vol.\ 2 (Keszthely, 1993) (Vol. 2, pp. 353–397). Budapest: János Bolyai Math. Soc.
  5. A good cross-section through applications of spectral graph theory:
    Mohar, B. (1997). Some applications of Laplace eigenvalues of graphs. In Graph symmetry (Montreal, PQ, 1996) (Vol. 497, pp. 225–275). Dordrecht: Kluwer Acad. Publ.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s