Graph Theory

Last update: 30 Jul 2026 12:23
First version: 14 July 2015

---

Yet another inadequate place to stash references.

---- I mean by this, incidentally, mathematical theory about abstract graphs, which primarily interests me because I want to use them as models of real-world networks...

See also:
• Graph limits and infinite exchangeable arrays
• Graph sampling algorithms
• Graph spectra
• Network comparsions
• Network topology and synchronization
• Random Fields (including random fields on graphs)

Recommended, big picture:
• Rick Durrett, Random Graph Dynamics
• M. E. J. Newman, Networks: An Introduction

Recommended, close-ups:
• Itai Benjamini, Nicolas Curien, "Ergodic Theory on Stationary Random Graphs", arxiv:1011.2526
• Fan Chung, Spectral Graph Theory
• Nathan Linial, Eran London and Yuri Rabinovich, "The geometry of graphs and some of its algorithmic applications", Combinatorica 15 (1995): 215--245 [PDF conference version]
• Terence Tao, "Szemerédi's regularity lemma revisited", arxiv:math/0504472

To read:
• L. Barnett, C. L. Buckley, S. Bullock, "A Graph Theoretic Interpretation of Neural Complexity", arxiv:1011.5334
• Arthur Benjamin, Gary Chartrand and Ping Zhang, The Fascinating World of Graph Theory
• Vincent Blondel, Anahi Gajardo, Maureen Heymans, Pierre Senellart, Paul Van Dooren, "A measure of similarity between graph vertices", cs.IR/0407061
• Fan Chung and Linyuan Lu, Complex Graphs and Networks
• Reinhard Diestel, Graph Theory
• Ted Dobson, Aleksander Malnic, and Dragan Marusic, Symmetry in Graphs
• Ben D. MacArthur, Rubén J. Sánchez-García, James W. Anderson, "On Automorphism Groups of Networks", Discrete Applied Mathematics 156 (2008): 3525--3531, arxiv:0705.3215
• Anatolii A. Puhalskii, "Stochastic processes in random graphs", math.PR/0402183 [Large deviations for Erdos-Renyi graphs. Memo to self: how much work would it be to extend this to Markovian graphs?]
• A. Rapoport
  • "Contribution to the theory of random and biased nets", Bulletin of Mathematical Biophysics 19 (1957): 257--277
  • "Cycle distribution in random nets", Bulletin of Mathematical Biophysics 10 (1968): 145--157
• Gunther Schmidt, Relational Mathematics
• Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, Karsten M. Borgwardt, "Weisfeiler-Lehman Graph Kernels", Journal of Machine Learning Research 12 (2011): 2539--2561
• R. Solomonoff and A. Rapoport, "Connectivity of Random Nets", Bulletin of Mathematical Biophysics 13 (1951): 107--117 [Yes, the R. Solomonoff]
• S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, Karsten M. Borgwardt, "Graph Kernels", Journal of Machine Learning Research 11 (2010): 1201--1242 ["Graphs become ever so much easier to understand when you project them into a Hilbert space." (Not an actual quote.)]
• Nicholas C. Wormald
  • "Differential Equations for Random Processes and Random Graphs", Annals of Applied Probability 5 (1995): 1217--1235
  • "The differential equation method for random graph processes and greedy algorithms" ["Notes on lectures given at the Summer School on Randomized Algorithms at Antonin, Poland in 1997"; PDF]