Graphs and Network Theory Summary

GRAPHS AND NETWORKS
Acyclic
• a graph that contains no cycles, e.g. a tree (a connected, acyclic graph)
• trees are maximally acyclic (taking away any edge makes it not acyclic anymore)
• a forest is a disconnected acyclic graph
• G a tree ⟺ any 2 vertices in G are connected by a unique path ⟺ G is acyclic and
|𝐸| = |𝑉| − 1
• used to prove Euler’s Formula
• Grőtzsch

Adjacency Matrix
1 𝑖𝑓 {𝑖, 𝑗} ∈ 𝐸
• 𝐴 is a 𝑛 × 𝑛 matrix with entries 𝐴𝑖𝑗 = {
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
1 𝑖𝑓 𝑖 → 𝑗 ∈ 𝐸
• directed graphs: 𝐴𝑖𝑗 = {
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
• multigraphs: 𝐴𝑖𝑗 = number of edges between 𝑖 and 𝑗
• 𝐴𝑛 = the matrix of n-step walks
• Perron-Frobenius
[𝐴3 ]
• Clustering: if 𝑑(𝑖) ≥ 2 then 𝐶(𝑖) = 𝑑(𝑖)(𝑑(𝑖)−1)
𝑖𝑖


• Kirchhoff’s Matrix Tree Theorem: 𝐷 the diagonal matrix, then 𝐿 = 𝐷 − 𝐴 has evalues:
1
𝜇1 ≥ ⋯ ≥ 𝜇𝑛−1 ≥ 𝜇𝑛 = 0 and the # of spanning trees of G is ∏𝑛−1𝑖=1 𝜇𝑖
𝑛
• bipartite: iff the spectrum of 𝐴 is symmetric about zero
𝜆 (𝐴)
• Hoffman: 𝒳(𝐺) ≥ 1 − 𝜆1 (𝐴) (largest and smallest evalues of 𝐴)
𝑛


Art Gallery Theorem
• polygon: a planar region bounded by 𝑛 straight edges (also called an 𝒏-gon)
• 𝑥 in a polygon 𝑃 sees 𝑦 in 𝑃 if the straight line 𝑥𝑦 is contained in 𝑃
𝑛
• AGT: no more than 3 points are required to jointly see the whole of an 𝑛-gon

Bipartite Graphs
• bipartite if 𝑉 can be a disjoint union 𝑉 = 𝑋 ∪ 𝑌, where 𝑋 ∩ 𝑌 = ∅, every edge is of the form
𝑒 = 𝑥𝑦, 𝑥 ∈ 𝑋, 𝑦 ∈ 𝑌
• complete bipartite: 𝐾𝑛,𝑚 has |𝑋| = 𝑛, |𝑌| = 𝑚 and every possible edge
• trees are bipartite
• a graph is bipartite iff it contains no cycles of odd length
• 𝐴 must have a spectrum that is symmetric about zero
• chromatic number: bipartite iff 𝒳(𝐺) ≤ 2

Chromatic Numbers
• 𝒳(𝐺) is the smallest 𝑘 such that G is 𝑘-colourable
• for all 𝑘 ≥ 3 ∃ graphs with chromatic # at least 𝑘 and girth at least 𝑘
• 𝒳(𝐺) ≤ 1 + max 𝛿(𝐻)
𝐻⊆𝐺
𝜆 (𝐴)
• Hoffman: 𝒳(𝐺) ≥ 1 − 𝜆1 (𝐴) (largest and smallest evalues of 𝐴)
𝑛

, Clustering Coefficients
• local clustering coefficient:
# 𝑜𝑓 𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑖𝑛𝑔 𝑣 # 𝑜𝑓 𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑖𝑛𝑔 𝑣
𝐶(𝑣) = # 𝑜𝑓 𝑝𝑎𝑖𝑟𝑠 𝑜𝑓 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟𝑠 𝑜𝑓 𝑣 = # 𝑜𝑓 𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑖𝑛𝑔 𝑣 + # 𝑜𝑓 𝑛𝑜𝑛−𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠 𝑤𝑖𝑡ℎ 𝑚𝑖𝑑𝑑𝑙𝑒 𝑣
1
• mean clustering coefficient: 𝐶(𝐺) = |𝑉| ∑𝑣∈𝑉 𝐶(𝑣)
[𝐴3 ]
• if 𝑑(𝑖) ≥ 2 then 𝐶(𝑖) = 𝑑(𝑖)(𝑑(𝑖)−1)
𝑖𝑖


𝑁𝑐
• ER-I random graphs: 𝑀 = so that 〈𝑑〉 = 𝑐, as 𝑁 → ∞, 𝐶(𝑖) → 0 zero clustering
2
• Configuration models: 𝐶(𝐺) ~ 𝑁 −1

Contagion Threshold
• contagion process: where transmissibility 𝑇 ∈ [0,1], initially one vertex infected, one
chance to infect each neighbour, repeated until no further transmission
1
• contagion threshold - 𝑇𝑐 ≔ 𝜆 and 𝒉 = 𝑇𝑐 𝐻𝒉 the top evalue
𝑚𝑎𝑥(𝐻)

i. if 𝑇 < 𝑇𝑐 then 𝑟𝑖 = 0 for all 𝑖
ii. if 𝑇 = 𝑇𝑐 + 𝜀 for 𝜀 ≪ 1 then 𝑟𝑖 ∝ 𝜀 ∑𝑗~𝑖 ℎ𝑗𝑖
iii. if 𝑇 = 1 − 𝜀 for 𝜀 ≪ 1 then 𝑟𝑖 ≈ 1 − 𝜀 𝑑(𝑖)
• model networks: G a config. model r.g with degree dist 𝑝𝑑 with 𝑔(𝑥) = ∑𝑑 𝑥 𝑑 𝑝𝑑 and
ℎ(𝑥) = ∑𝑑 𝑥 𝑑 𝑞𝑑
1
• contagion threshold (model networks): 〈𝑇𝑐 〉 = ℎ′ (1) = (∑𝑑 𝑑𝑞𝑑 )−1

Critical Graphs
• 𝒌-critical: a 𝑘-colourable graph G is 𝑘-critical if 𝒳(𝐺) = 𝑘
• 𝐾𝑛 is n-critical
• if G is 𝑘-critical, then it is connected and 𝛿(𝐺) ≥ 𝑘 − 1

Crossing Number
• crossing number: the number of pairs of edges that share interior points
• 𝑐𝑟(𝐺) is the smalled crossing number possible in a plane drawing of 𝐺
• if 𝑐𝑟(𝐺) = 0 then 𝐺 is planar, and a plane drawing with no crossing is called a plane graph
𝑚 𝑚−1 𝑛 𝑛−1
• 𝑐𝑟(𝐾𝑛,𝑚 ) = ⌊ 2 ⌋ ⌊ ⌋ ⌊2⌋ ⌊ ⌋
2 2
4|𝐸|3
• for all 𝐺 with 𝑑(𝐺) > 8: 𝑐𝑟(𝐺) ≥
243|𝑉|2
• for all 𝐺 with |𝑉| ≥ 3, |𝐸| ≥ 3 : 𝑐𝑟(𝐺) ≥ |𝐸| − 3|𝑉| + 6

Definitions
• ALL IN NOTES

Degree distributions
1
• 𝑖=1 𝛿𝑑(𝑖),𝑑 [the fraction of vertices of degree d]
𝑝𝑑 = 𝑁 ∑𝑁
(𝑑+1)𝑝(𝑑+1)
• excess degree dist: 𝑞𝑑 ≔ if randomly chosen 𝑢~𝑣 then ℙ(𝑑(𝑣) = 𝑑 + 1) = 𝑞𝑑
𝑑(𝐺)
𝑁𝑐 𝑐 𝑑 𝑒 −𝑐
• ER-I random graphs: 𝑀 = so that 〈𝑑〉 = 𝑐, as 𝑁 → ∞, 𝑝𝑑 → Poisson degree dist
2 𝑑!
• configuration model: 𝒢(𝑁, 𝑑) has given degree sequence d, or degree dist 𝑝𝑑