I read following fact:
Size of perfect matching $≤$ size of minimum edge cover
Doubts:
- 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.
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.
Can we say:
Perfect independent set (whenever it exists) is a minimum vertex cover?
PS:
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:
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