Global forcing number for maximal matchings (CROSBI ID 246208)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Vukičević, Damir ; Zhao, Shuang ; Sedlar, Jelena ; Xu, Shou-Jun ; Došlić, Tomislav
engleski
Global forcing number for maximal matchings
Let $\mathcal{; ; ; M}; ; ; (G)$ denote the set of all maximal matchings in a simple graph $G$, and $f: \mathcal{; ; ; M}; ; ; (G) \rightarrow\{; ; ; 0, 1\}; ; ; ^{; ; ; |E(G)|}; ; ; $ be the characteristic function of maximal matchings of $G$. Any set $S \subseteq E(G)$ such that $f \big | _{; ; ; 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.
global forcing set ; global forcing number ; maximal matching
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
341 (3)
2018.
801-809
objavljeno
0012-365X
1872-681X
10.1016/j.disc.2017.12.002