The saturation number is a structural invariant related to matchings. Let G be a graph with edge set EðGÞ: M � EðGÞ is a maximal matching if it is not a subset of some other matching in graph G: The smallest possible number of edges in a maximal matching of G is called the saturation number. Determining the saturation number of a graph is an NP-hard problem. The aim of this paper is to study the Tabu Search (TS) algorithm for solving this problem. The proposed algorithm can be implemented on general graphs. However, in our computational tests, TS found a saturation number for fullerene graphs, and we compared the obtained results with the methods presented in other studies.

Keywords