The strong matching number of a random graph (Q2760456)

The strong matching number sm(\(G\)) of a graph \(G\) is the size of the largest induced matching in \(G\). Fix \(0<p<1\) and create \(G\) randomly on \(n\rightarrow\infty\) vertices with edge probability \(p\). It is shown that almost every \(G\) has sm(\(G\)) equal to either \(m\) or \(m-1\) where \(m\) is given explicitly in terms of \(n\) and \(p\). The probability of achieving each of these two values is calculated, as is the distribution of the number of induced matchings of size sm(\(G\)). The concentration result for sm(\(G\)) improves an earlier result by \textit{A. El Maftouhi} and \textit{L. Marquez Gordones} [Australas. J. Comb. 10, 97-104 (1994; Zbl 0817.05054)].