Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903095 | Discrete Mathematics | 2018 | 9 Pages |
Abstract
Let M(G) denote the set of all maximal matchings in a simple graph G, and f:M(G)â{0,1}|E(G)| be the characteristic function of maximal matchings of G. Any set SâE(G) such that f|S is an injection is called a global forcing set for maximal matchings in G, and the cardinality of smallest such S is called the global forcing number for maximal matchings of G. In this paper we establish sharp lower and upper bounds on this quantity and prove explicit formulas for certain classes of graphs. At the end, we also state some open problems and discuss some further developments.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Damir VukiÄeviÄ, Shuang Zhao, Jelena Sedlar, Shou-Jun Xu, Tomislav DoÅ¡liÄ,