Smallest maximal matchings of graphs

Abstract

Let $G=(V_G, E_G)$ be a simple and connected graph. A set $M\subseteq E_G$ 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 $\Delta$.

Keywords

• maximal matching
• product graph
• saturation number
• independent domination number

References

1. [1] R. B. Allan and R. Laskar On domination and independent domination numbers of a graph, Discrete Math. 23, 73-76, 1978.
2. [2] V. Andova, T. Došlić, M. Krnc, B. Lužar and R. Škrekovski, On the diameter and some related invariants of fullerene graphs, MATCH Commun. Math. Comput. Chem. 68, 109-130, 2012.
3. [3] V. Andova, F. Kardoš and R. Škrekovski, Sandwiching saturation number of fullerene graphs, MATCH Commun. Math. Comput. Chem. 73, 501-518, 2015.
4. [4] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
5. [5] T. Biedl, E. D. Demaine, S. G. Kobourov, C. A. Duncan and R. Fleischer, Tight bounds on maximal and maximum matchings, Discrete Math. 285, 7-15, 2004.
6. [6] J.A. Bondy and U.S.R. Murty, Graph theory, Graduate Texts in Mathematics, vol. 244. Springer, New York, 2008.
7. [7] G. Chartrand and L. Lesniak, Graphs & Digraphs, CRC Press, 2010.
8. [8] M. Demange and T. Ekim, Minimum maximal matching is NP-hard in regular bipartite graphs, Conference on Theory and Applications of Models of Computations, LNCS 4978, pp. 364–374, 2008.

9. [9] T. Došlić, Saturation number of fullerene graphs, J. Math. Chem. 43, 647-657, 2008.
10. [10] T. Došlić, Block allocation of a sequential resource, Ars Math. Contemp. 17, 79-88, 2019.
11. [11] T. Došlić and I. Zubac, Saturation Number of Benzenoid Graphs, MATCH Commun. Math. Comput. Chem. 73, 491-500, 2015.
12. [12] T. Došlić and I. Zubac, Counting maximal matchings in linear polymers, Ars Math. Contemp. 11, 255-276, 2016.
13. [13] D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Combin. Theory B 19, 87-95, 1975.
14. [14] W. Goddard and M. A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313, 839-854, 2013.
15. [15] I. Gutman and S. J. Cyvin, Introduction to the Theory of Benzenoid Hydrocarbons, Springer Verlag, Berlin, Heidelberg, 1989.
16. [16] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Taylor & Francis Group, 2011.
17. [17] J.D. Horton and K. Kilakos, Minimum edge dominating sets, SIAM J. Disc. Math. 6, 375-387, 1993.
18. [18] L. Lovász and M. D. Plummer, Matching Theory, North-Holland, Amsterdam, 1986.
19. [19] N. Tratnik and P. Žigert Pleteršek, Saturation Number of Nanotubes, Ars Math. Contemp. 12, 337-350, 2017.
20. [20] D.B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 1996.
21. [21] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38, 364-372, 1980.
22. [22] M. Zito, Small maximal matchings in random graphs, Theoret. Comput. Sci. 297, 487-507, 2003.