Coverings | Engineering Mathematics - Civil Engineering (CE) PDF Download

Introduction

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 line/edge covering. A subgraph which contains all the edges is called a vertex covering.

Line Covering

Its subgraphs having line 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

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 line coverings, while C4 is not because we can delete {b, c}.

Minimum Line Covering

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

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

• Every line covering contains a minimal line covering.
• Every line covering does not contain a minimum line covering (C3 does not contain any minimum line covering.
• No minimal line covering contains a cycle.
• If a line covering ‘C’ contains no paths of length 3 or more, then ‘C’ is a minimal line 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 K4 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.