Special Mathematics Lecture
Contact:
Serge Richard (richard@math.nagoyau.ac.jp), Rm. 247 in Sci. Bldg. A
Graph theory (Spring 2024)
Registration code : 0053621
Schedule : Wednesday (18.30  20.00) in room 207 of Science Building A and on Zoom

SML official rule :
See here

Class dates :
April 10, 17, 24
May 1, 8, 15, 22, 29
June 5, 12, 19, 26
July 3, 10, 17 (oral exam)

Program (tentative) :
1) The basics
2) Representations and structures
3) Trees
4) Spanning trees
5) Connectivity
6) Optimal traversals
7) Graph colorings
8) Directed graphs
9) Flows
10) Random graphs: the G(n;p) model
11) The configuration model
12) Epidemics on graphs

Weekly summaries :
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
13,
14,

Study sessions :
Will be organized on an individual basis by some international students

Evaluation :
You need to submit the solutions of some exercises and/or the proofs of some statements.
These submissions can take place at any time during the semester.
If you have any question, contact me
or the TA Sota Kitano.

Student's reports :
Inequalitities between the radius and the diameter of a finite graph, by Yat Ming Luk
On cycles of a bipartite graph, by Firdaus Rafi Rizqy
Graphic sequence and HavelHakimi Theorem, by Firdaus Rafi Rizqy
On Eulerian graphs, by Vic Austen
Six different characterizations of a tree, by Firdaus Rafi Rizqy and Saranakomkoop Sirawich
River crossing puzzles, by Oleh Dmytruk
Graph invariants: order and size, by Wich Moonsarn
Order of odd regular graphs, by Hevidu Samarakoon and Riichi Yatagai
The number of odd degree vertices is even, by Hevidu Samarakoon and Riichi Yatagai
Some properties of d dimensional cubes, by Muyan Ding
A lemma about unoriented trees, by Adam Matefy
Prüfer encoding and a proof of Cayley's tree formula, by Nguyen Tue Tai
Number of insertion sequences resulting in a balanced search tree, by Kanae Iwata
On powers of adjacency matrices, by Kris Sukanan
HavelHakimi algorithm for determining graphic sequences, by Loren Holl
Path detection with disjoint sets, by Loren Holl
Proving Catalan recurrence theorem, by Firdaus Rafi Rizqy and Saranakomkoop Sirawich
Kirchhoff's matrixtree theorem, by Oleh Dmytruk
BEST theorem, by Yang MingTian
Proof of 2connectivity using disjoint paths, by AlbertoJohn Thornton and Nozomu Takeichi
On connectivity, by Ngo Gia Linh and Hirao Momona
Whitney Synthesis, by Muyan Ding
Breadthfirst search trees and one application, by Ngo Gia Linh
Transformation from incidence matrix to adjacency matrix of undirected graph implemented in C, by Wich Moonsarn and Jeffrey Zhang
Eulerian properties, by Ngo Gia Linh and Hirao Momona
Insert and delete for BST, by Vilem Fiala
Ramsey Theorem, by Nguyen Tue Tai
Travelling Salesman Problem (TSP), by AlbertoJohn Thornton and Vilem Fiala
Equivalence of loops and bridges in dual graph, by Nozomu Takeichi
Two nonHamiltonian graphs, by AlbertoJohn Thornton and Nozomu Takeichi
AVL Tree, by Vilem Fiala
The bipartite graph recognition theorem, by Chengxun Wu
Dirac's theorem, by Chengxun Wu
On finding the longest Eulerian path with multiple edges, by Byzov Martin
On the application of BellmanFord algorithm, by Byzov Martin
Proof of the five color theorem, by Yinan Rao
Menger's theorem, by Chengxun Wu
Proof of Berge's theorem, by Yinan Rao
Proof of Brooks' theorem, by Yinan Rao
Relationship between matrix and walks, by Narumi Ota
A greedybased approximation algorithm for maximum matching, by Yang MingTian
Calculation of strongly connected components in graphs, by Yijiang Liu
Maximumbipartitematching and Hall's marriage theorem, by Shino Susaki
Trading card exchanges, by Deric Yeap
Utilising adjacency matrices in biological systems: a focus on disease modelling, by AlbertoJohn Thornton
Kruskal's algorithm for minimum spanning tree generation, by Loren Holl and Kanae Iwata
SIR model with Leslie matrices approach and why it does not work, by Wich Moonsarn
Triangle detection in graphs, by Loren Holl and Kanae Iwata

References : (electronic version available upon request)
[BG] S. Baase, A. van Gelder, Computer algorithms, Introduction to design and analysis, AddisonWesley.
Useful for understanding some algorithms
[Bol] B. Bollobas, Modern graph theory, Springer. Classical textbook, more advanced
[CZ] G. Chartrand, P. Zhang, A first course in graph theory, Dover. Another possible textbook
[CH] J. Clark, D.A. Holton, A first look at graph theory, World Scientific. An easily accessible book
[Die] R. Diestel, Graph theory, Springer. A classical book
[GYA] J.L. Gross, J. Yellen, M. Anderson, Graph theory and its applications, CRC press. Our initial main reference
[KMS] I. Kiss, J. Miller, P. Simon,
Mathematics of epidemics on networks, Springer, 2017.
The main reference for the last lecture, seems very good
[KK] W. Kocay, D.L. Kreher, Graphs, algorithms, and optimization, 2nd edition, Chapman and Hall. With algorithms
[Ma] B. Maurer, The King Chicken Theorems. A very nice introduction to the king of chickens
[Mo] J.W. Moon, Topics on tournaments, Holt, Rinehart and Winston, Inc. Everything you want to know on tournaments
[Ne] M. Newman, Networks, second edition, Oxford University Press. One of the most recent books on networks, lot of text, but understandable
[Wal] W.D. Wallis, A beginner's guide to graph theory, Birkhauser. An introduction to the subject, NOT TOO BIG
Back to the main page