2016/03/22 by Ajayi, Deborah Olayide, Adefokun, Tayo Charles
#05C15 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1603.06967
An induced matching M in a graph G is a matching in G that is also the edge set of an induced subgraph of G. That is, any edge not in M must have no more than one incident vertex saturated by M. The maximum size |M| of an induced matching M of G is maximum induced matching number of G, which is denoted by \textrmMax(G). In this article, we obtain upper bounds for \textrmMax(G), for G=Gn,m, grids with n,m ≥ 9, m≡ 1 \mod 4 and nm odd.