On maximum induced matching numbers of special grids

• Autorzy: Adefokun T. C. , Ajayi D. O.

Identyfikatory

DOI

10.7862/rf.2018.1

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

induced matching; grid; maximum induced matching number; strong matching number

PL

skojarzenie; krata; liczba skojarzona

• Wydawca: Oficyna Wydawnicza Politechniki Rzeszowskiej
• Czasopismo: Journal of Mathematics and Applications
• Rocznik: 2018
• Tom: Vol. 41
• Strony: 5--18
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Adefokun T. C.

• Department of Computer and Mathematical Sciences, Crawford University, Nigeria

autor

Ajayi D. O.

• Department of Mathematics University of Ibadan, Ibadan, Nigeria

Bibliografia

• [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 owers, 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.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).