Graph Theory
Last update: 07 Apr 2026 23:06First 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
- 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.)]