Vertex Covering

VERTEX COVERING
A subset W of V is called a vertex covering or a vertex cover of G if every edge in G is incident on at least one vertex in W.

Trivial vertex covering: A vertex cover of a graph is a subgraph of the graph, V it self is a vetex covering of G. This is known as the trivial vertex covering.

Minimal vertex covering: A vertex covering W of G is called a minimal vertex covering if no proper subset of W is a vertex covering of G.

For example. In the graph shown in Fig. 7.1(b) below, the set W = {v2, v4, v6} is a vertex covering.
We check that {v1, v2}, {v1, v3}, {v2, v3}, {v1}, {v2}, {v3} are not vertex coverings of the graph.
Thus, no proper subset of W is a vertex covering. Hence W is a minimal vertex covering.

EDGE COVERING
A non empty subset S of E is called an edge covering or an edge cover of G if every non isolated vertex in G is inciedent with at least one edge in S.

Trivial edge covering: An edge cover of a graph is a subgraph of the graph, E itself is an edge covering of G. This is known as the trivial edge covering.

Minimal edge covering: An edge covering S of G is called a minimal edge covering if no proper subset of S is an edge covering of G.

For example. In Figure 7.1(b), the set S = {e1, e3, e6, e8} is an edge covering.

INDEPENDENCE: A set of points in G is independent if no two of them are adjacent.

Point independence number: The largest number of points in such a set is called the point is independence number of G and is denoted by β0 (G) or β0.

Line independence number: An independent set of lines of G has no two of its lines adjacent and the maximum cardinality of such a set is the line independence number β1 (G) or β1.
For the complete graph, β0 (KP) = 1 and β1 (KP) = [P/2].
From the above graph, β0 (G) = 2 and β1(G) = 3.