Graph Theory

Graph Theory or Network Theory is a branch of discrete mathematics that has been treated with great importance and is expanding its scope with endless applications in recent times. It is inherently visualization-friendly and algorithm-friendly, making it a field close to computer science and data science. Ironically, the proof process often involves more words than equations, making it a challenging subject for mathematicians. Regardless of personal preferences, studying graph theory is never a waste of time, and it can be recommended to undergraduates without the need for prerequisites.

Basics

• Graphs and Networks
  • Isomorphism
  • Homeomorphism
• 🔒(24/08/28) Definition of Hypergraph

Spectral

• Matrix Representation of Graphs
• Degree $\deg$
  • Handshaking Lemma
  • Handshaking Dilemma

Topology

• Set Representation of Graphs
  • Subgraphs
• Distance, Neighborhood, Diameter, Girth $d$, $N$, $\text{diam}$, $\text{girth}$
• Graph Complement $\overline{G}$

Deterministic Graphs

Named Graphs

• Null Graph and Complete Graph $K_{n}$
• Regular Graphs
• Bipartite Graphs $G(A,B)$
• Infinite Graphs
  • Kőnig’s Theorem
• Erdős–Gallai Theorem
• Havel-Hakimi Algorithm
• Tree Graphs
  • Labeled Trees and Cayley’s Formula
• Null Graphs
  • Anderson-Livingston Theorem
• Perfect Graphs

Path Problems

• Walks, Trails, Paths, Cycles
  • Orientation of Graphs
• Eulerian Graphs
  • Königsberg Bridge Problem and Solution
  • Fleury’s Algorithm
• Hamiltonian Graphs
  • Dirac’s Theorem

Four Color Problem

• Planar Graphs and Kuratowski’s Theorem
  • Euler’s Polyhedral Formula
  • Properties of Simple Planar Graphs
• Graph Coloring and Brooks’ Theorem
• Graph k-Connectivity and Menger’s Theorem
• Geometric Dual Graphs
• Abstract Dual Graphs
• Definition of Maps in Graph Theory
• Five Color Theorem
• Four Color Map Problem

Nondeterministic Networks

Random Networks

• Graph Families and Properties $2^{\binom{n}{2}}$, $\mathscr{G}_{n,m}$
• Random Networks $\mathbb{G}$
  • Degree Distribution
• Erdős–Rényi Model $\mathbb{G}_{n,m}$
  • Gilbert Model $\mathbb{G}_{n,p}$
• Scale-Free Networks
  • Chung-Lu Fitness Model
  • Barabási-Albert Model
• Euclidean Networks

Centrality

• Hub Nodes
• Degree Centrality
• Betweenness Centrality
  • Stress Centrality
• Closeness Centrality
• Eigenvector Centrality

Practice

• Gephi: Graph Visualization and Analysis Software
• NetworkX: Python Package for Graph Analysis
  • Reading and Writing GEXF Files
• Graphs.jl: Julia Package for Graph Analysis

References

• Albert, Barabási. (2002). Statistical mechanics of complex networks
• Barabási. (2016). Network Science
• Brouwer. (2011). Spectra of Graphs
• Frieze. (2015). Introduction to Random Graphs
• Newman. (2010). Networks: An Introduction
• Wilson. (1970). Introduction to Graph Theory