Chapter A · Appendix
Notation and Symbols
Every symbol this book uses, the standard complexity table, and the terminology that differs between communities.
Graphs
| symbol | meaning | first used |
|---|---|---|
| G=(V,E), n=|V|, m=|E| | the graph and its sizes | A Zoo of Graphs |
| N(v), N[v] | open / closed neighbourhood of v | A Zoo of Graphs |
| deg(v), δ(G), Δ(G) | degree, minimum and maximum degree | A Zoo of Graphs |
| bar G | complement | Subgraphs, Minors and Operations |
| G[S], G - S | induced subgraph, deletion of a vertex set | Subgraphs, Minors and Operations |
| G/e, G - e | edge contraction, edge deletion | Contraction, Induction and Lifting |
| H ≼m G | H is a minor of G (deletions + contractions) | Planarity and Euler's Formula |
| ω(G), α(G), χ(G), χ'(G) | clique, independent set, chromatic, chromatic index | Graph Colouring |
| κ(G), λ(G) | vertex- and edge-connectivity | Connectivity, Bridges, Articulation Points |
| G^* | planar dual | Planarity and Euler's Formula |
| ecc(v), rad(G), diam(G) | eccentricity, radius, diameter | Tree Diameter in Two Passes |
| cen(G) | centre (one vertex or an edge) | Tree Diameter in Two Passes |
| dist(u,v) | shortest-path distance (number of edges, or ∑ weights) | Distance, Radius, Eccentricity |
| Akuv | number of walks of length k from u to v | Counting Walks with Matrix Powers |
| L = D - A, τ(G) | Laplacian, number of spanning trees | The Matrix–Tree Theorem |
| tin[v], tout[v] | DFS entry/exit times | Entry/Exit Times and the Euler Tour |
| depth[v], par[v], sub[v] | rooted-tree depth, parent, subtree size | Depth-First Search |
| lca(u,v) | lowest common ancestor | The LCA Problem |
| M, ν(G), μ(G) | a matching, its maximum size (two conventions) | Matching: Definitions and Duality |
| τv(G) | minimum vertex cover size (some books write β) | Kőnig's Theorem and Minimum Covers |
| R(s,t), Rk(3) | Ramsey numbers | Ramsey Theory on Graphs |
| Δ, ∇ | max degree; also the Laplacian operator in Random Walks and Cover Times | — |
Complexity and asymptotics
| notation | meaning |
|---|---|
| O(f), Ω(f), Θ(f) | upper, lower, both — and in this book O(·) is worst-case unless "expected" is written |
| tilde O(f) | O(f logc f) for some constant c |
| [n] | the set {1,…,n} (or {0,…,n-1} in code) |
| C(n, k) | binomial coefficient; logC(n, k) ≤ klog(en/k), used in Ramsey Theory on Graphs |
| x mod p, x-1 | residue in [0,p); multiplicative inverse mod prime p |
| α ≤ β + ε n | the "+o(n)"-style sloppiness in approximation statements |
| P, NP, NP-hard, NP-complete | P, NP, and Reductions — What You Actually Need |
| FPT, XP | fixed-parameter tractable: f(k) nO(1) versus nf(k) — Escape Routes: What To Do When It Is NP-Hard |
| 3-SAT, CLIQUE, 3-DIM MATCHING | the standard sources of reductions (The NP-complete Graph Problems Worth Knowing) |
The complexity table you should be able to recite
| bound at n = 105 | verdict |
|---|---|
| O(n), O(nlog n) | fine — up to 107–108 operations |
| O(n√n) ≈ 3·107 | fine |
| O(nlog2 n), O(nlog n) with big constants | fine, watch the memory |
| O(n2) = 1010 | too slow; O(n2) is only OK up to n ≈ 5000 |
| O(n2/64) bitset | 1.5·108 word-ops — passes; the kind of trick Independent Sets, Cliques, and Treewidth is about |
| O(2n n) | n ≤ 22 (Escape Routes: What To Do When It Is NP-Hard's Held–Karp bound) |
| O(3n/3), O(1.2n) | n ≤ 40–60 — measure and conquer territory |
| O(n!) | n ≤ 10 |
NoteWhere this book's terminology differs from other sources
- "walk" vs "path" vs "trail": a walk repeats freely, a trail repeats no edge, a path repeats no vertex. Upstream and several Russian texts use "path" for walks; Walks, Trails, Paths, Cycles fixes the convention used here,
- connected: this book says "connected component" for maximal connected subgraphs and never calls a disconnected graph "connected with k parts",
- DFS order:
tin/touthere mean entry/exit timer values (not "the i-th visited vertex"); interval containment is the whole point (Entry/Exit Times and the Euler Tour), - tree DP states are written (v, 0/1) for "not taken/taken" — the same skeleton as Independent Sets, Cliques, and Treewidth,
- matching duality: ν for matching size and τ for cover size, following Vizing/Kőnig usage; some books use α' and β,
- 0-indexed vs 1-indexed: the code uses 0-based arrays, the math uses [n]. When a proof says "the parent of the root is itself", that is the code convention (The LCA Problem),
- log is base 2 inside complexity claims and base e inside probabilistic ones (Random Walks and Cover Times), and it never changes an O(·).
Function and value names used in the code, once
g adjacency list · w weight (function or matrix) · dist best known distance · par, dep, sub parent/depth/subtree size · tin, tout DFS times · up[v][j] 2j-ancestor · dp[...] table · nxt functional-graph successor · mt match partner · lvl, ptr Dinic/HK layer and cursor · comp component id · INF, LINF sentinels · ret, res accumulator in a function.