On Maximum Induced Matching Numbers of Special Grids

A subset M of the edge set of a graph G is an induced matching of G if given any two edges e1, e2 ∈ M, none of the vertices on e1 is adjacent to any of the vertices on e2. Suppose that Max(G), a positive integer, denotes the maximum size of M in G, then, M is the maximum induced matching of G and Max(G) is the maximum induced matching number of G. In this work, we obtain upper bounds for the maximum induced matching number of grid G = G_{n,m}, n ≥ 9, m ≡ 3 mod 4, m ≥ 7, and nm odd.

Full text (pdf)

1. D.O.A. Ajayi, T.C. Adefokun, Some bounds of the maximum induced matching numbers of certain grids, Acta Universitatis Matthiae Belii, Series Mathematics 25 (2017) 63-71 (Online version available at http://actamath.savbb.sk).
2. K. Cameron, Induced matching in intersection graphs, Discrete Math. 278 (2004) 1-9.
3. K. Cameron, R. Sritharan, Y. Tang, Finding a maximum induced matching in weakly chordal graphs, Discrete Math. 266 (2003) 133-142.
4. K.K. Dabrowski, M. Demange, V.V. Lozin, New results on maximum induced matchings in bipartite graphs and beyond, Theoretical Computer Science 478 (2013) 33-40.
5. J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965) 449-467.
6. M.C. Golumbic, R.C. Laskar, Irredundancy in circular arc graphs, Discrete Applied Math. 44 (2013) 79-89.
7. C. Lane, The strong matching number of a random graph, Australasian Journal of Combinatorics 24 (2001) 47-57.
8. H. Michel, M. Lalla, Maximum induced matching algorithms via vertex ordering characterizations, arXiv: 1707.01245 (2017).
9. R. Marinescu-Ghemeci, Maximum induced matchings in grids, Springer Proceedings in Math. and Stat. 31 (2012) 177-187.
10. L.J. Stockmeyer, V.V. Vazirani, NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters 15 (1982) 14-19.
11. M. Zito, Induced Matching in Regular Graphs and Trees, Lecture Notes in Computer Sci. 1665, Springer, Berlin, 1999.