Understanding relation between independent set and covers

184 Views Asked by At

I read following fact:

Size of perfect matching $≤$ size of minimum edge cover

Doubts:

  1. Shouldn't perfect matching (whenever it exists) always be an edge cover? and hence should have same size as that of minimum edge cover (making above fact incorrect)?

Matching is nothing but independent edge set. So, I was trying to find out independent set-vertex cover equivalent of above fact.

  1. First thing, can concept of "perfect independent vertex set" exist (, because I have never read about it anywhere online and in reference books) ? I tried defining it myself as follows:

    Set of vertices no two of which are adjacent to each other and each edge is incident on at least one vertex of the set.

    After re-reading this self prepared definition, I feel such concept can exist.

  2. Can we say:

    Perfect independent set (whenever it exists) is a minimum vertex cover?

PS:

1

There are 1 best solutions below

2
On

Shouldn't perfect matching (whenever it exists) always be an edge cover? and hence should have same size as that of minimum edge cover (making above fact incorrect)?

A perfect matching is also a minimum edge cover. The inequality should refer to maxiumum matching : $$\text{Size of maximum matching }\leq \text{size of minimum edge cover}$$ A minium edge cover can be found by finding a maximum matching and extending it greedily so that all vertices are covered.

You also have the following general result:

Given a connected graph, the number of edge of its minimum edge cover plus its maximum matching is equal to the number of vertices

Regarding your definition of perfect independent set. Sure I guess you could define it that way, but there are already some similar concept : you might want to have a look at minimal dominating sets, and domination-perfect graph