Global forcing number of grid graphs (CROSBI ID 137907)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Vukičević, Damir ; Došlić, Tomislav
engleski
Global forcing number of grid graphs
Let $G$ be a simple connected graph with a perfect matching. Let ${; ; ; \cal M}; ; ; (G)$ denote the set of all perfect matchings in $G$, and $f: {; ; ; \cal M}; ; ; (G) \rightarrow \{; ; ; 0, 1\}; ; ; ^{; ; ; |E(G)|}; ; ; $ a characteristic function of perfect matchings of $G$. Any set $S \subseteq E(G)$ such that $f \left | _S \right .$ is an injection is called a global forcing set in $G$, and the cardinality of smallest such $S$ is called the global forcing number of $G$. In this paper we first establish lower bounds on this quantity and show how it can be computed for certain classes of composite graphs, and then we prove an explicit formula for global forcing number of the grid graph $R_{; ; ; p, q}; ; ; = P_p \times P_q$. We also briefly consider a vertex global forcing number of grid graphs and present an explicit formula for it. In the last section we give explicit formulas for global forcing numbers of complete graphs and discuss some further developments.
global forcing number; grid graph
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano