Applied Graph Theory: Connectivity

CS4L006 :Applied Graph Theory
Connectivity
Joy Mukherjee
Schoolof ElectricalSciences
Computer Science and Engineering
Indian Institute of Technology Bhubaneswar
1 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
2 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
3 / 39

Vertex Cut & Connectivity
Definition
Separating Set / Vertex Cut (VC (G )) = {S|S ⊆ V (G ) ∧ G \ S has more
than one component}.
Definition
The conectivity of (G), written as κ(G ), is the minimum size of a vertex
set S such that V \ S is disconnected or has only one vertex.
Definition
A graph is k-connected if its connectivity is atleast k.A k-Connected
Graph (other than a complete graph) is a graph where every VC (G ) has at
least k vertices i.e.deletion of any (k − 1) vertices can not make it
disconnected.
4 / 39

Vertex Cut & Connectivity
κ(Kn) = n − 1.κ(K1) = 0.
κ(Km,n) = min{m, n}.
κ(Qk) = k.
κ(disconnected graph with more than one vertex) = 0.
A graph with more than two vertices has connectivity one iff it is
connected and has a cut-vertex.
5 / 39

Cut & Edge-Connectivity
Definition
Disconnecting Set (DS(G )) = {F |F ⊆ E (G ) ∧ G \ F has more than one
component}.
Definition
The edge-conectivity of (G), written as κ0(G ), is the minimum size of a
disconnecting set S such that V \ S is disconnected.
Definition
A graph is k-edge-connected if its edge-connectivity is atleast k.
k-Edge-Connected Graph is a graph where every DS(G ) has at least k
edges i.e.deletion of any (k − 1) edges can not make it disconnected.
6 / 39

Edge Cut
Definition
Given S , T ⊆ V (G ), [S , T ] is a set of edges having one endpoint in S and
the other endpoint in T .
Definition
Edge Cut = {[S, S]|S 6= φ ∧ S ⊂ V (G ) ∧ S = V (G ) \ S.Every minimal
disconnecting set is an edge cut.
Every edge cut is a disconnecting set but the converse is not true.
7 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
8 / 39