Nalazite se na CroRIS probnoj okolini. Ovdje evidentirani podaci neće biti pohranjeni u Informacijskom sustavu znanosti RH. Ako je ovo greška, CroRIS produkcijskoj okolini moguće je pristupi putem poveznice www.croris.hr
izvor podataka: crosbi

Global forcing number of grid graphs (CROSBI ID 137907)

Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija

Vukičević, Damir ; Došlić, Tomislav Global forcing number of grid graphs // Australasian journal of combinatorics, 38 (2007), 47-62

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

Podaci o izdanju

38

2007.

47-62

objavljeno

1034-4942

Povezanost rada

Matematika

Indeksiranost