Graph Theory - Coverings

A covering graph is a subgraph which contains either all the vertices or all the edges corresponding to some other graph. A subgraph which contains all the vertices is called a pne/edge covering. A subgraph which contains all the edges is called a vertex covering.

Line Covering

Let G = (V, E) be a graph. A subset C(E) is called a pne covering of G if every vertex of G is incident with at least one edge in C, i.e.,

deg(V) ≥ 1 ∀ V ∈ G

because each vertex is connected with another vertex by an edge. Hence it has a minimum degree of 1.

Example

Take a look at the following graph −

Its subgraphs having pne covering are as follows −

C₁ = {{a, b}, {c, d}}

C₂ = {{a, d}, {b, c}}

C₃ = {{a, b}, {b, c}, {b, d}}

C₄ = {{a, b}, {b, c}, {c, d}}

Line covering of ‘G’ does not exist if and only if ‘G’ has an isolated vertex. Line covering of a graph with ‘n’ vertices has at least [n/2] edges.

Minimal Line Covering

A pne covering C of a graph G is said to be minimal if no edge can be deleted from C.

Example

In the above graph, the subgraphs having pne covering are as follows −

C₁ = {{a, b}, {c, d}}

C₂ = {{a, d}, {b, c}}

C₃ = {{a, b}, {b, c}, {b, d}}

C₄ = {{a, b}, {b, c}, {c, d}}

Here, C₁, C₂, C₃ are minimal pne coverings, while C₄ is not because we can delete {b, c}.

Minimum Line Covering

It is also known as Smallest Minimal Line Covering. A minimal pne covering with minimum number of edges is called a minimum pne covering of ‘G’. The number of edges in a minimum pne covering in ‘G’ is called the pne covering number of ‘G’ (α₁).

Example

In the above example, C₁ and C₂ are the minimum pne covering of G and α₁ = 2.

Every pne covering contains a minimal pne covering.

Every pne covering does not contain a minimum pne covering (C₃ does not contain any minimum pne covering.

No minimal pne covering contains a cycle.

If a pne covering ‘C’ contains no paths of length 3 or more, then ‘C’ is a minimal pne covering because all the components of ‘C’ are star graph and from a star graph, no edge can be deleted.

Vertex Covering

Let ‘G’ = (V, E) be a graph. A subset K of V is called a vertex covering of ‘G’, if every edge of ‘G’ is incident with or covered by a vertex in ‘K’.

Example

Take a look at the following graph −

The subgraphs that can be derived from the above graph are as follows −

K₁ = {b, c}

K₂ = {a, b, c}

K₃ = {b, c, d}

K₄ = {a, d}

Here, K₁, K₂, and K₃ have vertex covering, whereas K₄ does not have any vertex covering as it does not cover the edge {bc}.

Minimal Vertex Covering

A vertex ‘K’ of graph ‘G’ is said to be minimal vertex covering if no vertex can be deleted from ‘K’.

Example

In the above graph, the subgraphs having vertex covering are as follows −

K₁ = {b, c}

K₂ = {a, b, c}

K₃ = {b, c, d}

Here, K₁ and K₂ are minimal vertex coverings, whereas in K₃, vertex ‘d’ can be deleted.

Minimum Vertex Covering

It is also known as the smallest minimal vertex covering. A minimal vertex covering of graph ‘G’ with minimum number of vertices is called the minimum vertex covering.

The number of vertices in a minimum vertex covering of ‘G’ is called the vertex covering number of G (α₂).

Example

In the following graph, the subgraphs having vertex covering are as follows −

K₁ = {b, c}

K₂ = {a, b, c}

K₃ = {b, c, d}

Here, K₁ is a minimum vertex cover of G, as it has only two vertices. α₂ = 2.