Hacettepe Journal of Mathematics & Statistics Hacet. J. Math. Stat. Volume XX (x) (XXXX), 1 – 11 DOI : 10.15672/hujms.xx Research Article Smallest maximal matchings of graphs Mostafa Tavakoli∗1, Tomislav Došlić2,3 1Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad 91775, Iran 2Faculty of Civil Engineering, University of Zagreb, Kačićeva 26, 10000 Zagreb, Croatia 3Faculty of Information Studies, Novo Mesto, Slovenia Abstract Let G = (VG, EG) be a simple and connected graph. A set M ⊆ EG is called a matching of G if no two edges of M are adjacent. The number of edges in M is called its size. A matching M is maximal if it cannot be extended to a larger matching in G. The smallest size of a maximal matching is called the saturation number of G. In this paper we are concerned with the saturation numbers of lexicographic product of graphs. We also address and solve an open problem about the size of maximum matchings in graphs with a given maximum degree ∆.

Keywords