Global Forcing Number for Maximal Matchings under Graph Operations

Document Type : بنیادی - نظری

Author

Ferdowsi University of Mashhad

10.30473/coam.2020.51754.1138

Abstract

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.

Keywords


bibitem{Ada}‎
‎Adams P.‎, ‎Mahdian M.‎, ‎Mahmoodian E.S‎. ‎(2004)‎. ‎``On the forced matching numbers of bipartite graphs"‎,
‎Discrete Mathematics‎, ‎281‎, ‎1--12‎.
 
‎bibitem{Afs}‎
‎Afshani P.‎, ‎Hatami H.‎, ‎Mahmoodian E. S‎. ‎(2004)‎. ‎``On the spectrum of the forced matching number of graphs"‎,
‎Australasian Journal of Combinatorics‎, ‎30‎, ‎147--160‎.
 
‎bibitem{Barr}‎
‎Barri'ere L.‎, ‎Dafl'o C.‎, ‎Fiol M‎. ‎A.‎, ‎Mitjana M‎. ‎(2009)‎. ‎``The generalized hierarchical product of graphs"‎,
‎Discrete Mathematics‎, ‎309‎, ‎3871--3881‎.
 
‎bibitem{Berg}‎
‎Berge C‎. ‎(1973)‎. ‎``Graphs and Hypergraphs"‎, ‎North-Holland‎, ‎Amsterdam‎.
 
‎bibitem{Caro}‎
‎Caro Y‎. ‎(1979)‎. ‎``New results on the independence number"‎, ‎Technical Report‎, ‎Tel-Aviv University‎.
 
‎bibitem{Har}‎
‎Harary F.‎, ‎Klein D. J.‎, ‎$check{Z}$ivkovi'c T. P‎. ‎(1991)‎. ‎``Graphical properties of polyhexes‎: ‎perfect matching vector and forcing"‎,
‎Journal of Mathematical Chemistry‎, ‎6‎, ‎295--306‎.
 
‎bibitem{Henn}‎
‎Henning M. A.‎, ‎L"{o}wenstein C.‎, ‎Southey J.‎, ‎Yeo A‎. ‎(2014)‎.
‎``A new lower bound on the independence number of a graph and applications"‎, ‎Electronic Journal of Combinatorics‎, ‎21‎,
‎1--38‎.
 
‎bibitem{Henning}‎
‎Henning M. A.‎, ‎Schiermeyer I.‎, ‎Yeo A‎. ‎(2011)‎.
‎``A new bound on the domination number of graphs‎
‎with minimum degree two"‎, ‎Electronic Journal of Combinatorics‎, ‎18‎, ‎12‎.
 
‎bibitem{klavzar}‎
‎Klav$check{z}$ar S.‎, ‎Tavakoli M‎. ‎(2020)‎.
‎``Local metric dimension of graphs‎: ‎Generalized hierarchical products and some applications"‎,
‎Applied Mathematics and Computation‎, ‎364‎, ‎124676‎.
 
‎bibitem{Kle}‎
‎Klein D. J.‎, ‎Randi'c M‎. ‎(1986)‎. ‎``Innate degree of freedom of a graph"‎, ‎Journal of Computational Chemistry‎, ‎8‎, ‎516--521‎.
 
‎bibitem{Fajt}‎
‎Fajtlowicz S‎. ‎(1978)‎. ‎``On the size of independent sets in graphs"‎, ‎Congressus Numerantium‎,
‎21‎, ‎269--274‎.
 
‎bibitem{Tava}‎
‎Tavakoli M.‎, ‎Rahbarnia F.‎, ‎Ashrafi A. R‎. ‎(2014)‎.
‎``Applications of the generalized hierarchical product of graphs in computing the vertex and edge‎
‎PI indices of chemical graphs"‎, ‎Ricerche di Matematica‎, ‎63‎, ‎59--65‎.
 
‎bibitem{Dos}‎
‎Vuki$check{c}$evi'c D.‎, ‎Zhao S.‎, ‎Sedlar J.‎, ‎Xu S. J.‎, ‎Do$check{s}$li'c T‎. ‎(2018)‎.
‎``Global forcing number for maximal matchings''‎,
‎Discrete Mathematics‎, ‎341‎, ‎801--809‎.
 
‎bibitem{Pac}‎
‎Pachter L.‎, ‎Kim P‎. ‎(1998)‎. ‎``Forcing matchings in square grids"‎, ‎Discrete Mathematics‎, ‎190‎, ‎287--294‎.
 
‎bibitem{Push}‎
‎Pushpalatha A. P.‎, ‎Jothilakshmi G.‎, ‎Suganthi S.‎, ‎Swaminathan V‎. ‎(2011)‎.
‎``Forcing independent spectrum in graphs"‎, ‎International Journal of Computer Applications‎, ‎21‎, ‎1--6‎.
 
‎bibitem{Rid}‎
‎Riddle M. E‎. ‎(2002)‎. ‎``The minimum forcing number for the torus and hypercube"‎, ‎Discrete Mathematics‎, ‎245‎, ‎283--292‎.
 
‎bibitem{song}‎
‎Song W.‎, ‎Miao L.‎, ‎Wang H.‎, ‎Zhao Y‎. ‎(2014)‎.
‎``Maximal matching and edge domination in complete‎
‎multipartite graphs"‎, ‎International Journal of Computer Mathematics‎,
‎91‎, ‎857--862‎.
 
‎bibitem{ids}‎
‎Sun L.‎, ‎Wang J‎. ‎(1999)‎. ‎``An upper bound for the independent‎
‎Domination Number"‎, ‎Journal of Combinatorial Theory‎. ‎Series B‎, ‎76‎, ‎240--246‎.
 
‎bibitem{Vuk}‎
‎Vuki$check{c}$evi'c D.‎, ‎Kroto H. W.‎, ‎Randi'c M‎. ‎(2005)‎. ‎``Atlas of Kekul'{e} valence structures of buckminsterfullerene"‎, ‎Croatica Chemica Acta‎, ‎78‎, ‎223--234‎.
 
‎bibitem{Vuki}‎
‎Vuki$check{c}$evi'c D.‎, ‎Randi'c M‎. ‎(2005)‎. ‎``On Kekul'e structures of buckminsterfullerene"‎, ‎Chemical Physics Letters‎, ‎401‎, ‎446--450‎.
 
‎bibitem{Wei}‎
‎Wei V‎. ‎(1981)‎. ‎``A lower bound on the stability number of a simple graph"‎,
‎Bell Laboratories Technical Memorandum 81-11217-9‎, ‎Murray Hill‎, ‎NJ‎.
 
‎bibitem{Zha}‎
‎Zhang F. J.‎, ‎Li X. L‎. ‎(1995)‎. ‎``Hexagonal systems with forcing edges"‎, ‎Discrete Mathematics‎, ‎140‎, ‎253--263‎.