参考文献
目次
[17s]Darij Grinberg, Notes on graph theory, draft of two chapters, 6th April 2023. https://www.cip.ifi.lmu.de/~grinberg/t/17s/nogra.pdf
[17s-lec7]Darij Grinberg, UMN, Spring 2017, Math 5707: Lecture 7 (Hamiltonian paths in digraphs), 14 May 2022. https://www.cip.ifi.lmu.de/~grinberg/t/17s/5707lec7.pdf
[17s-lec8]Darij Grinberg, UMN, Spring 2017, Math 5707: Lecture 8 (Vandermonde determinant using tournaments), 28 April 2023. https://www.cip.ifi.lmu.de/~grinberg/t/17s/5707lec8.pdf
[17s-lec16]Darij Grinberg, UMN, Spring 2017, Math 5707: Lecture 16 (flows and cuts in networks), 14 May 2022. https://www.cip.ifi.lmu.de/~grinberg/t/17s/5707lec16.pdf
[17s-mt2s]Math 5707 Spring 2017 (Darij Grinberg): midterm 2 with solutions. https://www.cip.ifi.lmu.de/~grinberg/t/17s/mt2s.pdf
[19fco]Darij Grinberg, Enumerative Combinatorics: class notes, 11 March 2023. http://www.cip.ifi.lmu.de/~grinberg/t/19fco/n/n.pdf
[20f]Darij Grinberg, Notes on mathematical problem solving, 10 February 2021. http://www.cip.ifi.lmu.de/~grinberg/t/20f/mps.pdf
[21f6]Darij Grinberg, Math 235 Fall 2021, Worksheet 6: Graphs and some of their uses, 13 April 2023. http://www.cip.ifi.lmu.de/~grinberg/t/21f/lec6.pdf
[21s]Darij Grinberg, An Introduction to Algebraic Combinatorics [Math 701, Spring 2021 lecture notes], 19 December 2022. https://www.cip.ifi.lmu.de/~grinberg/t/21s/lecs.pdf
[23wd]Darij Grinberg, Math 221: Discrete Mathematics, Winter 2023. https://www.cip.ifi.lmu.de/~grinberg/t/23wd/
[AbuSbe88]Moh'd Z. Abu-Sbeih, On the number of spanning trees of \(K_{n}\) and \(K_{m,n}\), Discrete Mathematics 84 (1990), pp. 205–207.
[AigZie18]Martin Aigner, Günter M. Ziegler, Proofs from the Book, 6th edition, Springer 2018.
[Alon02]Noga Alon, Combinatorial Nullstellensatz, 22 February 2002. http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf
[AloSpe16]Noga Alon, Joel H. Spencer, The Probabilistic Method, 4th edition, Wiley 2015.
[Aspnes23]James Aspnes, Notes on Randomized Algorithms (CPSC 469/569: Spring 2023), 1 May 2023. https://www.cs.yale.edu/homes/aspnes/classes/469/notes.pdf
[BapRag97]R. B. Bapat, T. E. S. Raghavan, Nonnegative Matrices and Applications, Cambridge University Press 1997.
[BenWil06]Edward A. Bender, S. Gill Williamson, Foundations of Combinatorics with Applications, Dover 2006. https://mathweb.ucsd.edu/~ebender/CombText/index.html
[BerFou91]J. C. Fournier and C. Berge, A Short Proof for a Generalization of Vizing's Theorem, Journal of Graph Theory 15 (1991), No. 3, pp. 333–336.
[Berge91]Claude Berge, Graphs, North-Holland Mathematical Library 6.1, 3rd edition, North-Holland 1991.
[BidKis02]Hoda Bidkhori, Shaunak Kishore, Counting the spanning trees of a directed line graph, arXiv:0910.3442v1. Later published under the title A Bijective Proof of a Theorem of Knuth, Combinatorics, Probability & Computing 20 (1), pp. 11–25, 2011.
[Bollob71]Bela Bollobas, Graph Theory: An Introductory Course, Springer 1971.
[Bollob98]Béla Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer 1998.
[BonMur08]J. A. Bondy, U.S.R. Murty, Graph theory, 3rd printing, Springer 2008.
[BonTho77]J. A. Bondy, C. Thomassen, A short proof of Meyniel's theorem, Discrete Mathematics 19, Issue 2, 1977, pp. 195–197.
[Brouwer09]Andries E. Brouwer, The number of dominating sets of a finite graph is odd, http://www.win.tue.nl/~aeb/preprints/domin2.pdf.
[ChDiGr92]Fan Chung, Persi Diaconis, Ron Graham, Universal cycles for combinatorial structures, Discrete Mathematics 110 (1992), pp. 43–59, http://www.math.ucsd.edu/~fan/wp/universalcycle.pdf.
[Chen14]Evan Chen, Expected Uses of Probability, 2014. https://web.evanchen.cc/handouts/ProbabilisticMethod/ProbabilisticMethod.pdf.
[ChLeZh16]Gary Chartrand, Linda Lesniak, Ping Zhang, Graphs \& Digraphs, 6th edition, CRC Press 2015.
[Conrad21]Keith Conrad, Universal identities, 13 February 2021. https://kconrad.math.uconn.edu/blurbs/linmultialg/univid.pdf.
[CorPer18]Scott Corry, David Perkinson, Divisors and Sandpiles, AMS 2018. A preprint is available at https://people.reed.edu/~davidp/divisors_and_sandpiles/mbk_draft.pdf.
[CraRab15]Daniel W. Cranston and Landon Rabern, Brooks' Theorem and Beyond, Journal of Graph Theory 80 (2015), issue 3, pp. 199–225. https://brianrabern.net/landon-papers/jgt21847.pdf
[DeLeen19]Patrick De Leenheer, An elementary proof of a matrix tree theorem for directed graphs, arXiv:1904.12221v1. Published in: SIAM Review 62/3 (2020), pp. 716–726.
[DHLetc19]Galen Dorpalen-Barry, Cyrus Hettle, David C. Livingston, Jeremy L. Martin, George Nasr, Julianne Vega, Hays Whitlatch, A positivity phenomenon in Elser's Gaussian-cluster percolation model, arXiv:1905.11330v6, corrected version of a paper published in: Journal of Combinatorial Theory, Series A, 179:105364, April 2021, doi:10.1016/j.jcta.2020.105364.
[Dieste17]Reinhard Diestel, Graph Theory, 5th Edition, Springer 2017. See https://diestel-graph-theory.com/GrTh5_corrections.pdf for errata.
[Elser84]Veit Elser, Gaussian-cluster models of percolation and self-avoiding walks, J. Phys. A: Math. Gen. 17 (1984), pp. 1515–1523.
[EngVat18]Michael Engen, Vincent Vatter, Containing all permutations, arXiv:1810.08252v4, Amer. Math. Monthly 128 (2021), pp. 4–24. https://arxiv.org/abs/1810.08252v4.
[Euler36]Leonhard Euler, Solutio problematis ad geometriam situs pertinentis, Euler Archive - All Works 53, 1741.
[EulerEn53]Leonhard Euler, James R. Newman, Leonhard Euler and the Koenigsberg bridges (English translation of "Solutio problematis ad geometriam situs pertinentis)", Scientific American 1953.
[ForFul74]L. R. Ford, Jr., D. R. Fulkerson, Flows in Networks, 7th printing, Princeton University Press, 1974.
[Freder82]Harold Fredricksen, A Survey of Full Length Nonlinear Shift Register Cycle Algorithms, SIAM Review 24, No. 2, April 1982, pp. 195–221. https://doi.org/10.1137/1024041
[FriFri98]Rudolf Fritsch, Gerda Fritsch, The Four-Color Theorem, translated by Julie Peschke, Springer 1998.
[Gallie13]Jean Gallier, Notes on Elementary Spectral Graph Theory. Applications to Graph Clustering Using Normalized Cuts, arXiv:1311.2492v1.
[Galvin21]David Galvin, Basic Discrete Mathematics (Spring 2021). https://www3.nd.edu/~dgalvin1/60610/60610_S21/index.html Follow the overleaf link. Notes:
Course-notes.tex; solved homework: main.tex.
[Gessel79]Ira Gessel, Tournaments and Vandermonde's Determinant, Journal of Graph Theory 3 (1979), pp. 305–307.
[Griffi21]Christopher Griffin, Graph Theory: Penn State Math 485 Lecture Notes, version 2.0, 2021.
[Grinbe20]Darij Grinberg, Notes on the combinatorial fundamentals of algebra, arXiv:2008.09862v3.
[Grinbe21]Darij Grinberg, The Elser nuclei sum revisited, arXiv:2009.11527v8. (More detailed version of a paper published in: Discrete Mathematics & Theoretical Computer Science 23 no. 1, Combinatorics (June 3, 2021) dmtcs:7487.)
[GrKaLe21]Darij Grinberg, Lukas Katthän, Joel Brewster Lewis, The path-missing and path-free complexes of a directed graph, arXiv:2102.07894v1.
[GrSaSu14]Daniel J. Gross, John T. Saccoman, Charles L. Suffel, Spanning tree results for graphs and multigraphs, World Scientific 2014.
[Guicha16]David Guichard, An Introduction to Combinatorics and Graph Theory, 4 March 2023, https://www.whitman.edu/mathematics/cgt_online/cgt.pdf .
[HaHiMo08]John Harris, Jeffry L. Hirst, Michael Mossinghoff, Combinatorics and Graph Theory, 2nd edition, Springer 2008. See https://www.appstate.edu/~hirstjl/bib/CGT_HHM_2ed_errata.html for errata.
[Hall35]Philip Hall, On representatives of subsets, J. London Math. Soc., 10/1 (1935), pp. 26–30.
[Hall45]Marshall Hall, An existence theorem for Latin squares, Bull. Amer. Math. Soc. 51, Number 6, Part 1 (1945), pp. 387–388.
[Harary69]Frank Harary, Graph theory, Addison-Wesley 1969.
[Harju14]Tero Harju, Lecture notes on Graph Theory, 24 April 2014. http://users.utu.fi/harju/graphtheory/graphtheory.pdf
[HarRin03]Nora Hartsfield, Gerhard Ringel, Pearls in Graph Theory, Dover 2003.
[HeiTit17]Irene Heinrich, Peter Tittmann, Counting Dominating Sets of Graphs, arXiv:1701.03453v1.
[HeiTit18]Irene Heinrich, Peter Tittmann, Neighborhood and Domination Polynomials of Graphs, Graphs and Combinatorics 34 (2018), pp. 1203–1216.
[HLMPPW13]Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, David B. Wilson, Chip-Firing and Rotor-Routing on Directed Graphs, arXiv:0801.3306v4. https://arxiv.org/abs/0801.3306v4.
[Holzer22]Fabian Holzer, Matrix Tree Theorems, diploma thesis at TU Wien. https://www.dmg.tuwien.ac.at/bgitten/Theses/holzer.pdf.
[JoyMel17]W. David Joyner, Caroline Grant Melles, Adventures in Graph Theory, Birkhäuser 2017.
[Jukna11]Stasys Jukna, Extremal Combinatorics, 2nd edition, Springer 2011. See https://web.vu.lt/mif/s.jukna/EC_Book_2nd/misprints-EC.html for errata.
[Jungni13]Dieter Jungnickel, Graphs, Networks and Algorithms, 4th edition, Springer 2013.
[KelTro17]Mitchel T. Keller, William T. Trotter, Applied Combinatorics, 2017. https://www.appliedcombinatorics.org/appcomb/get-the-book/
[Kirchh47]Gustav Robert Kirchhoff, Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird, Annalen der Physik und Chemie 148.12 (1847).
[KleSta19]Steven Klee, Matthew T. Stamps, Linear Algebraic Techniques for Spanning Tree Enumeration, arXiv:1903.04973v2.
[Klivan19]Caroline J. Klivans, The Mathematics of Chip-firing, CRC 2019. https://www.dam.brown.edu/people/cklivans/Chip-Firing.pdf.
[KrGrWi10]Alex Kruckman, Amy Greenwald, John Wicks, An elementary proof of the Markov chain tree theorem, 6 August 2010. https://math.berkeley.edu/~kruckman/MCTT.pdf.
[Landau53]H. G. Landau, On dominance relations and the structure of animal societies: III The condition for a score structure, The Bulletin of Mathematical Biophysics 15(2) (1953), pp. 143–148.
[LayMul98]Charles Laywine, Gary L. Mullen, Discrete mathematics using Latin squares, John Wiley & Sons, 1998.
[LeeShi19]Jonghyeon Lee, Heesung Shin, The chromatic polynomial for cycle graphs, arXiv:1907.04320v1. https://arxiv.org/abs/1907.04320v1.
[Leinst19]Tom Leinster, The probability that an operator is nilpotent, arXiv:1912.12562v2. Published in: The American Mathematical Monthly 128 (2021), Issue 4, pages 371–375.
[LeLeMe18]Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science, revised Tuesday 6th June 2018, https://courses.csail.mit.edu/6.042/spring18/mcs.pdf.
[LoPeVe03]Laszlo Lovasz, Jozsef Pelikan, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyound, Springer 2003. See https://www.math.colostate.edu/~adams/teaching/TyposMath301.pdf for some errata.
[MaOlAr11]Albert W. Marshall, Ingram Olkin, Barry C. Arnold, Inequalities: Theory of Majorization and Its Applications
[Margol10]Jonathan Margoliash, Matrix-Tree Theorem for Directed Graphs, REU paper at the University of Chicago, 2010. https://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/Margoliash.pdf.
[Maurer80]Stephen B. Maurer, The King Chicken Theorems, Mathematics Magazine 53 (1980), pp. 67–80.
[MirPer66]Leon Mirsky, Hazel Perfect, Systems of representatives, Journal of Mathematical Analysis and Applications 15, Issue 3, September 1966, pp. 520–568.
[MO232751]bof and Gordon Royle, MathOverflow question #232751 ("The number of Hamiltonian paths in a tournament"). https://mathoverflow.net/questions/232751/the-number-of-hamiltonian-paths-in-a-tournament.
[Moon13]John W. Moon, Topics on Tournaments, Project Gutenberg EBook, 5 June 2013. https://www.gutenberg.org/ebooks/42833.
[Moon70]John W. Moon, Counting Labelled Trees, Canadian Mathematical Monographs 1, 1970. https://www.math.ucla.edu/~pak/hidden/papers/Moon-counting_labelled_trees.pdf.
[Moreno04]Eduardo Moreno, On the theorem of Fredricksen and Maiorana about de Bruijn sequences, Advances in Applied Mathematics 33 (2004), pp. 413–415. https://doi.org/10.1016/j.aam.2003.10.002.
[Mutze14]Torsten Mütze, Proof of the middle levels conjecture, Proceedings of the London Mathematical Society 112 (4), 2016, pp. 677–713. See http://www.arxiv.org/abs/1404.4442v3 for a preprint.
[Mutze22]Torsten Mütze, Combinatorial Gray codes-an updated survey, arXiv:2202.01280v3.
[Ore74]Oystein Ore, Theory of graphs, American Mathematical Society Colloquium Publication 38, 4th printing, AMS 1974.
[Ore96]Oystein Ore, Graphs and their uses, New Mathematical Library 34, AMS 1990.
[Otter48]Richard Otter, The Number of Trees, The Annals of Mathematics, 2nd Ser. 49, No. 3. (Jul., 1948), pp. 583–599.
[Rubey00]Martin Rubey, Counting Spanning Trees, diploma thesis at Universität Wien. http://chanoir.math.siu.edu/MATH/MatrixTree/rubey.pdf.
[Ruohon13]Keijo Ruohonen, Graph theory, 2013. https://www.freetechbooks.com/graph-theory-t1080.html.
[Sahi14]Siddhartha Sahi, Harmonic vectors and matrix tree theorems, Journal of Combinatorics 5, Number 2, pp. 195–202, 2014.
[Schrij03]Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer 2003. See https://homepages.cwi.nl/~lex/co/ for errata.
[Schrij04]Lex Schrijver, Vizing's theorem for simple graphs, 26 August 2004. https://homepages.cwi.nl/~lex/files/vizing.pdf.
[Schrij17]Alexander Schrijver, A Course in Combinatorial Optimization, March 23, 2017. https://homepages.cwi.nl/~lex/files/dict.pdf.
[Smith15]Frankie Smith, The Matrix-Tree Theorem and Its Applications to Complete and Complete Bipartite Graphs, 11 May 2015. http://www.austinmohr.com/15spring4980/paper final draft.pdf.
[Stanle18]Richard P. Stanley, Algebraic Combinatorics: Walks, Trees, Tableaux, and More, 2nd edition, Springer 2018. See https://math.mit.edu/~rstan/algcomb/errata2.pdf for errata.
[Steele04]J. Michael Steele, The Cauchy–Schwarz Master Class, Cambridge University Press 2004. See http://www-stat.wharton.upenn.edu/~steele/Publications/Books/CSMC/CSMC_errat_Index.html for errata.
[Tait21]Mike Tait, Math 8790: Graph Theory, Spring 2021, 2021. https://sites.google.com/view/michaeltait/teaching-spring-2021.
[Treil17]Sergei Treil, Linear Algebra Done Wrong, 4 September 2017. https://www.math.brown.edu/streil/papers/LADW/LADW.html.
[VanEhr51]Tanja van Aardenne-Ehrenfest, Nicolaas Govert de Bruijn, Circuits and trees in oriented linear graphs, Simon Stevin 28 (1951), pp. 203–217.
[Verstr21]Jacques Verstraete, Introduction to Graph Theory, 3 February 2021. https://mathweb.ucsd.edu/~gmckinley/154_sp22/book.html.
[Vos16]Vaya Sapobi Samui Vos, Methods for determining the effective resistance, Master's thesis, 20 December 2016. https://www.universiteitleiden.nl/binaries/content/assets/science/mi/scripties/master/vos_vaya_master.pdf.
[West01]Douglas Brent West, Introduction to Graph Theory, 2nd edition, Pearson 2001. See https://faculty.math.illinois.edu/~west/igt/ for errata.
[Whitney32]Hassler Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc., Volume 38, Number 8 (1932), pp. 572–579. https://projecteuclid.org/euclid.bams/1183496087.
[Wilson10]Robin J. Wilson, Introduction to Graph Theory, 5th edition, Pearson 2010.
[Zhao23]Yufei Zhao, Graph Theory and Additive Combinatorics, Cambridge University Press 2023.