Global Forcing Number for Maximal Matchings under Graph Operations

Let S= \{e_۱,\,e_۲‎, ‎\ldots,\,e_m\} be an ordered subset of edges of a connected graph G‎. ‎The edge S-representation of an edge set M\subseteq E(G) with respect to S is the‎ ‎vector r_e(M|S) = (d_۱,\,d_۲,\ldots,\,d_m)‎, ‎where d_i=۱ if e_i\in M and d_i=۰‎ ‎otherwise‎, ‎for each i\in\{۱,\ldots‎ , ‎k\}‎. ‎We say S is a global forcing set for maximal matchings of G‎ ‎if r_e(M_۱|S)\neq r_e(M_۲|S) for any two maximal matchings M_۱ and M_۲ of G‎. ‎A global forcing set for maximal matchings of G with minimum cardinality is called‎ ‎a minimum global forcing set for maximal matchings‎, ‎and its cardinality‎, ‎denoted by \varphi_{gm}‎, ‎is the‎ ‎global forcing number (GFN for short) for maximal matchings‎. ‎Similarly‎, ‎for an ordered subset F = \{v_۱,\,v_۲‎, ‎\ldots,\,v_k\} of V(G)‎, ‎the F-representation of a vertex set I\subseteq V(G) with respect to F is the‎ ‎vector r(I|F) = (d_۱,\,d_۲,\ldots,\,d_k)‎, ‎where d_i=۱ if v_i\in I and‎ ‎d_i=۰ otherwise‎, ‎for each i\in\{۱,\ldots‎ , ‎k\}‎. ‎We say F is a global forcing set for independent dominatings of G‎ ‎if r(D_۱|F)\neq r(D_۲|F) for any two maximal independent dominating sets D_۱ and D_۲ of G‎. ‎A global forcing set for independent dominatings of G with minimum cardinality is called‎ ‎a minimum global forcing set for independent dominatings‎, ‎and its cardinality‎, ‎denoted by \varphi_{gi}‎, ‎is the‎ ‎GFN for independent dominatings‎. ‎In this paper, we study the GFN for maximal matchings‎ ‎under several types of graph products‎. ‎Also‎, ‎we present some upper bounds for this invariant‎. ‎Moreover‎, ‎we present some bounds for \varphi_{gm} of some well-known graphs.

کلیدواژه ها:

Global forcing set‎ ، ‎Global forcing number‎ ، ‎Maximal matching‎ ، ‎Maximal independent dominating‎ ، ‎Product graph