Smallest maximal matchings of graphs

Authors : Mostofa TAVAKOLİ, ‎tomislav DOSLİC

Pages : 356-366

Doi:10.15672/hujms.1095437

View : 26 | Download : 11

Publication Date : 2023-03-31

Article Type : Research Paper

Abstract :Let $G=insert ignore into journalissuearticles values(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