2021/12/31 by Matsuda, Kazunori, Yoshida, Yuichi
#Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics
paper · doi:10.48550/arxiv.2112.15297
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) ≤ \lfloor |V(G)|/2 \rfloor 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 \rmreg(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 \rmreg(G) = \rmreg(K[V(G)]/I(G)) is the Castelnuovo--Mumford regularity of the quotient ring K[V(G)]/I(G).