Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Czasopismo
Rocznik
Tom
Strony
5--18
Opis fizyczny
Bibliogr. 11 poz., rys.
Twórcy
autor
- Department of Computer and Mathematical Sciences, Crawford University, Nigeria
autor
- 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-42fa13cb-fbc8-4b3f-8f8b-45eae3565bd7