The minimum number of vertices and edges of connected graphs with ind-match$(G)=p$, min-match$(G)=q$ and match$(G)=r$

Abstract

Let ind-match$(G)$, min-match$(G)$ and match$(G)$ denote the induced matching number, minimum matching number and matching number of a graph $G$, respectively. It is known that ind-match$(G)\le$ min-match$(G)\le \mathrm{match}(G)\le$ 2min-match$(G)$ holds. In the present paper, we investigate the minimum number of vertices and edges of connencted simple graphs $G$ with ind-match$(G)=p$, min-match$(G)=q$ and $\mathrm{match}(G)=r$ for pair of integers $p,q,r$ such that $1\le p\le q\le r\le 2q$.

21 pages, 5 figures, add Section 4