The strong matching number of a random graph.
Lane Clark · 2001
lclark©math.siu.edu The strong matching number sm ( G) of a graph G is the maximum number of edges in G that induces a matching in the graph. For fixed o < p < 1, El Maftouhi and Marquez Gordones [Australasian Journal of Combinatorics 10 (1994), 97-104] showed that sm(Gn,p) is one of only a finite number of values for a.e. Gn,p E 9 (n, p). We show that, in fact, sm(Gn,p) is one of only two possible values for a.e. Gn,p E 9(n,p); determine the probability of attaining each value; and find the limiting distribution of the number of maximum strong matchings in Gn,p E 9(n,p). 1.