Global Forcing Number for Maximal Matchings under Graph Operations

Let S= \{e_1,\,e_2‎, ‎\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_1,\,d_2,\ldots,\,d_m)‎, ‎where d_i=1 if e_i\in M and d_i=0‎ ‎otherwise‎, ‎for each i\in\{1,\ldots‎ , ‎k\}‎. ‎We say S is a global forcing set for maximal matchings of G‎ ‎if r_e(M_1|S)\neq r_e(M_2|S) for any two maximal matchings M_1 and M_2 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_1,\,v_2‎, ‎\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_1,\,d_2,\ldots,\,d_k)‎, ‎where d_i=1 if v_i\in I and‎ ‎d_i=0 otherwise‎, ‎for each i\in\{1,\ldots‎ , ‎k\}‎. ‎We say F is a global forcing set for independent dominatings of G‎ ‎if r(D_1|F)\neq r(D_2|F) for any two maximal independent dominating sets D_1 and D_2 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 Number for Maximal Matchings under Graph Operations Keywords:

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