This paper investigates minimum vertices and edges in connected graphs with ind-match, min-match, and matching numbers, indicating relationships among these metrics.
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) ≤ min-match(G) ≤ match(G) ≤ 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 match(G) = r for pair of integers $p, q, r$ such that 1 ≤ p ≤ q ≤ r ≤ 2q.
No takes yet. Share an insight, caveat, or question.
Matsuda et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: