Nasze serwisy używają informacji zapisanych w plikach cookies. Korzystając z serwisu wyrażasz zgodę na używanie plików cookies zgodnie z aktualnymi ustawieniami przeglądarki, które możesz zmienić w dowolnej chwili. Więcej informacji odnośnie plików cookies.

Obowiązek informacyjny wynikający z Ustawy z dnia 16 listopada 2012 r. o zmianie ustawy – Prawo telekomunikacyjne oraz niektórych innych ustaw.

Wyłącz komunikat

 
 

Logowanie

Logowanie za pomocą Centralnej Usługi Uwierzytelniania PRz. Po zakończeniu pracy nie zapomnij zamknąć przeglądarki.

Journal of Mathematics and Applications

Journal of Mathematics and Applications
01/41, DOI: 10.7862/rf.2018.1

On Maximum Induced Matching Numbers of Special Grids

Tayo Charles Adefokun, Deborah Olayide Ajayi

DOI: 10.7862/rf.2018.1

Abstract

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)

References

  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.

About this Article

TITLE:
On Maximum Induced Matching Numbers of Special Grids

AUTHORS:
Tayo Charles Adefokun (1)
Deborah Olayide Ajayi (2)

AUTHORS AFFILIATIONS:
(1) Department of Computer and Mathematical Sciences, Crawford University, NIGERIA
(2) Department of Mathematics, University of Ibadan, Ibadan, NIGERIA
 

JOURNAL:
Journal of Mathematics and Applications
01/41

KEY WORDS AND PHRASES:
Induced matching; Grid; Maximum induced matching number; Strong matching number

FULL TEXT:
http://doi.prz.edu.pl/pl/pdf/jma/64

DOI:
10.7862/rf.2018.1

URL:
http://dx.doi.org/10.7862/rf.2018.1

RECEIVED:
2017-11-09

COPYRIGHT:
Publishing House of Rzeszow University of Technology Powstańców Warszawy 12, 35-959 Rzeszow

POLITECHNIKA RZESZOWSKA im. Ignacego Łukasiewicza; al. Powstańców Warszawy 12, 35-959 Rzeszów
tel.: +48 17 865 11 00, fax.: +48 17 854 12 60
Administrator serwisu:

Deklaracja dostępności | Polityka prywatności