Graph Theory

A comprehensive reference covering graph theory from elementary definitions through structural theory, algorithms, algebraic methods, probabilistic models, computational complexity, and modern applications in fourteen parts with appendices.

15 items

Graph Theory Reference

Part I. Foundations of Graph Theory

Chapter Title
1 What Graph Theory Is
2 Basic Definitions
3 Vertices and Edges
4 Graph Representations
5 Degree of a Vertex
6 Walks, Trails, and Paths
7 Cycles and Circuits
8 Connected Graphs
9 Components
10 Isomorphism
11 Subgraphs
12 Graph Operations
13 Complement Graphs
14 Graph Invariants
15 Classes of Graphs

Part II. Directed and Weighted Graphs

Chapter Title
16 Directed Graphs
17 In-Degree and Out-Degree
18 Directed Paths and Cycles
19 Strong Connectivity
20 Directed Acyclic Graphs
21 Topological Ordering
22 Weighted Graphs
23 Multigraphs
24 Hypergraphs
25 Signed and Labeled Graphs

Part III. Trees and Forests

Chapter Title
26 Trees
27 Forests
28 Rooted Trees
29 Binary Trees
30 Spanning Trees
31 Minimum Spanning Trees
32 Prüfer Sequences
33 Tree Traversal
34 Tree Decomposition
35 Applications of Trees

Part IV. Planar and Geometric Graphs

Chapter Title
36 Planar Graphs
37 Plane Embeddings
38 Euler's Formula
39 Faces and Regions
40 Kuratowski's Theorem
41 Graph Coloring of Planar Graphs
42 Dual Graphs
43 Geometric Graphs
44 Intersection Graphs
45 Computational Geometry Connections

Part V. Connectivity and Network Structure

Chapter Title
46 Vertex Connectivity
47 Edge Connectivity
48 Cuts and Cut Sets
49 Bridges and Articulation Points
50 Menger's Theorem
51 Network Reliability
52 Expansion and Expanders
53 Graph Separators
54 Sparse and Dense Graphs
55 Random Walks on Graphs

Part VI. Matching and Covering

Chapter Title
56 Matchings
57 Perfect Matchings
58 Hall's Marriage Theorem
59 Bipartite Matching
60 Maximum Matching Algorithms
61 Vertex Covers
62 Edge Covers
63 Independent Sets
64 Cliques
65 Dominating Sets

Part VII. Coloring Theory

Chapter Title
66 Vertex Coloring
67 Edge Coloring
68 Chromatic Number
69 Chromatic Polynomial
70 Greedy Coloring
71 Brooks' Theorem
72 Perfect Graphs
73 Ramsey Theory
74 List Coloring
75 Fractional Coloring

Part VIII. Algebraic Graph Theory

Chapter Title
76 Adjacency Matrices
77 Incidence Matrices
78 Laplacian Matrices
79 Spectrum of a Graph
80 Eigenvalues and Eigenvectors
81 Spectral Theorems
82 Algebraic Connectivity
83 Expander Graphs
84 Graph Energy
85 Cayley Graphs
86 Automorphism Groups

Part IX. Probabilistic and Random Graphs

Chapter Title
87 Random Graph Models
88 Erdős-Rényi Graphs
89 Threshold Phenomena
90 Small-World Networks
91 Scale-Free Networks
92 Preferential Attachment
93 Percolation on Graphs
94 Probabilistic Methods
95 Random Processes on Networks

Part X. Graph Algorithms

Chapter Title
96 Graph Traversal Algorithms
97 Breadth-First Search
98 Depth-First Search
99 Shortest Paths
100 Dijkstra's Algorithm
101 Bellman-Ford Algorithm
102 Floyd-Warshall Algorithm
103 Network Flow
104 Maximum Flow Algorithms
105 Minimum Cut Algorithms
106 Matching Algorithms
107 Union-Find Structures
108 Dynamic Graph Algorithms
109 Approximation Algorithms
110 Randomized Algorithms

Part XI. Computational Complexity

Chapter Title
111 Complexity Classes
112 NP-Complete Graph Problems
113 Hamiltonian Paths and Cycles
114 Traveling Salesman Problem
115 Graph Isomorphism Problem
116 Parameterized Complexity
117 Fixed-Parameter Tractability
118 Approximation Hardness

Part XII. Advanced Topics

Chapter Title
119 Extremal Graph Theory
120 Turán-Type Problems
121 Szemerédi Regularity Lemma
122 Minor Theory
123 Robertson-Seymour Theory
124 Infinite Graphs
125 Topological Graph Theory
126 Category-Theoretic Graphs
127 Simplicial Complexes
128 Graph Limits
129 Temporal Graphs
130 Quantum Graph Theory

Part XIII. Applications

Chapter Title
131 Social Networks
132 Web Graphs
133 Search Engines and PageRank
134 Biological Networks
135 Chemical Graph Theory
136 Electrical Networks
137 Transportation Networks
138 Communication Networks
139 Compiler Dependency Graphs
140 Knowledge Graphs
141 Recommendation Systems
142 Machine Learning on Graphs
143 Graph Neural Networks
144 Distributed Systems
145 Blockchain and Peer-to-Peer Networks

Part XIV. Specialized Structures

Chapter Title
146 Bipartite Graphs
147 Complete Graphs
148 Regular Graphs
149 Interval Graphs
150 Chordal Graphs
151 Comparability Graphs
152 Perfect Graphs
153 Tournament Graphs
154 Grid Graphs
155 De Bruijn Graphs
156 Kneser Graphs
157 Petersen Graph
158 Ramanujan Graphs

Appendices

Appendix Title
A Set Theory and Relations
B Proof Techniques
C Linear Algebra for Graph Theory
D Probability Review
E Algorithms and Complexity
F Mathematical Notation
G Historical Development
H Common Graph Families
I Theorem Index
J Symbol Index

This structure moves from elementary graph concepts toward structural theory, algorithms, algebraic methods, probabilistic models, and modern applications. It supports both pure mathematical treatment and computational graph systems used in computer science, networks, optimization, and machine learning.

Writes › Book › Graph Theory ›

I. Foundations of Graph Theory

Basic definitions, vertices and edges, graph representations, degree, walks, paths, cycles, connectivity, isomorphism, subgraphs, and classes of graphs — the bedrock of graph theory.
graph-theory mathematics book
Writes › Book › Graph Theory ›

II. Directed and Weighted Graphs

Directed graphs, in-degree and out-degree, directed paths and cycles, strong connectivity, DAGs, topological ordering, weighted graphs, multigraphs, hypergraphs, and labeled graphs.
graph-theory mathematics book
Writes › Book › Graph Theory ›

III. Trees and Forests

Trees, forests, rooted and binary trees, spanning trees, minimum spanning trees, Prüfer sequences, tree traversal, tree decomposition, and applications of trees.
graph-theory mathematics book
Writes › Book › Graph Theory ›

IV. Planar and Geometric Graphs

Planar graphs, plane embeddings, Euler's formula, faces, Kuratowski's theorem, coloring of planar graphs, dual graphs, geometric graphs, and connections to computational geometry.
graph-theory mathematics book
Writes › Book › Graph Theory ›

V. Connectivity and Network Structure

Vertex and edge connectivity, cuts, bridges, articulation points, Menger's theorem, network reliability, expanders, separators, and random walks on graphs.
graph-theory mathematics book
Writes › Book › Graph Theory ›

VI. Matching and Covering

Matchings, perfect matchings, Hall's marriage theorem, bipartite matching, maximum matching algorithms, vertex and edge covers, independent sets, cliques, and dominating sets.
graph-theory mathematics book
Writes › Book › Graph Theory ›

VII. Coloring Theory

Vertex and edge coloring, chromatic number, chromatic polynomial, greedy coloring, Brooks' theorem, perfect graphs, Ramsey theory, list coloring, and fractional coloring.
graph-theory mathematics book
Writes › Book › Graph Theory ›

VIII. Algebraic Graph Theory

Adjacency, incidence, and Laplacian matrices, graph spectrum, eigenvalues and eigenvectors, spectral theorems, algebraic connectivity, expander graphs, graph energy, Cayley graphs, and automorphism groups.
graph-theory mathematics book
Writes › Book › Graph Theory ›

IX. Probabilistic and Random Graphs

Random graph models, Erdős-Rényi graphs, threshold phenomena, small-world and scale-free networks, preferential attachment, percolation, probabilistic methods, and random processes on networks.
graph-theory mathematics book
Writes › Book › Graph Theory ›

X. Graph Algorithms

Graph traversal, BFS, DFS, shortest paths, Dijkstra, Bellman-Ford, Floyd-Warshall, network flow, maximum flow, minimum cut, matching algorithms, union-find, dynamic graph algorithms, approximation, and randomized algorithms.
graph-theory mathematics book
Writes › Book › Graph Theory ›

XI. Computational Complexity

Complexity classes, NP-complete graph problems, Hamiltonian paths and cycles, the traveling salesman problem, graph isomorphism, parameterized complexity, fixed-parameter tractability, and approximation hardness.
graph-theory mathematics book
Writes › Book › Graph Theory ›

XII. Advanced Topics

Extremal graph theory, Turán-type problems, Szemerédi regularity lemma, minor theory, Robertson-Seymour theory, infinite graphs, topological and category-theoretic graph theory, simplicial complexes, graph limits, temporal graphs, and quantum graph theory.
graph-theory mathematics book
Writes › Book › Graph Theory ›

XIII. Applications

Social networks, web graphs, PageRank, biological and chemical networks, electrical and transportation networks, compiler graphs, knowledge graphs, recommendation systems, graph neural networks, distributed systems, and blockchain networks.
graph-theory mathematics book
Writes › Book › Graph Theory ›

XIV. Specialized Structures

Bipartite, complete, and regular graphs, interval and chordal graphs, comparability and perfect graphs, tournaments, grid graphs, De Bruijn graphs, Kneser graphs, the Petersen graph, and Ramanujan graphs.
graph-theory mathematics book
Writes › Book › Graph Theory ›

Appendices

Reference material: set theory and relations, proof techniques, linear algebra for graph theory, probability review, algorithms and complexity, mathematical notation, historical development, common graph families, theorem index, and symbol index.
graph-theory mathematics book