The Saturation Number Problem Of Some Graphs

Let G be a simple connected graph.A matching in graph G refers to a set of edges of G such that any two of them are not adjacent.Futher,a matching M of G is maximal if there is no other matching for G which really contains M.The saturation number of graph G is the cardinality of any smallest maximal matching of G.This article considers the saturation numbers of some special graph classes,which are divided into four chapters.The first part is introduction,mainly introduce definitions,marks,backgrounds,progression,etc.In the second part,we give sharp lower bound n-2/3-h5/9 and[n/3]by the discharge method for(4,5,6)-fullerene graph and(3,6)-fullerene graph of order n respectively,where h5 is the number of pentagonal faces.Moreover,we show some examples of reaching the lower bound and propose two conjectures about the upper bound of saturation number for(4,6)-fullerene and(3,6)-fullerene graph respectively.At the third part,we mainly give the sharp lower bound[p/3]for rectangular grid graph and rectangular grid graph on the torus of order p,then give the upper bound of its saturation number by the construction method,and finally give the lower bound 1/3-1/18q+12 of the benzenoid parallelogram Pp,q;The last part is a summary of the results obtained in this article and the subsequent prospects,pointing out the direction and main content of further research.