On the three graph invariants related to matching of finite simple graphs

Abstract

Let G be a finite simple graph on the vertex set V(G) and let ind-match(G), min-match(G) and match(G) denote the induced matching number, the minimum matching number and the matching number of G, respectively. It is known that the inequalities ind-match(G) <= min-match(G) <= match(G) <= 2min-match(G) and match(G) <= |V(G)|/2 hold in general. 

In the present paper, we determine the possible tuples (p, q, r, n) with ind-match(G) = p, min-match(G) = q, match(G) = r and |V(G)| = n arising from connected simple graphs. As an application of this result, we also determine the possible tuples (p`, q, r, n) with reg(G) = p`, min-match(G) = q, match(G) = r and |V(G)| = n arising from connected simple graphs, where I(G) is the edge ideal of G and reg(G) = reg(K[V(G)]/I(G)) is the Castelnuovo--Mumford regualrity of the quotient ring K[V(G)]/I(G).