Napredna pretraga

Pregled bibliografske jedinice broj: 328539

Global forcing number of grid graphs


Vukičević, Damir; Došlić, Tomislav
Global forcing number of grid graphs // Australasian Journal of Combinatorics, 38 (2007), 47-62 (međunarodna recenzija, članak, znanstveni)


Naslov
Global forcing number of grid graphs

Autori
Vukičević, Damir ; Došlić, Tomislav

Izvornik
Australasian Journal of Combinatorics (1034-4942) 38 (2007); 47-62

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Global forcing number; grid graph

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika



POVEZANOST RADA


Projekt / tema
037-0000000-2779 - Diskretna matematika i primjene (Dragutin Svrtan, )
177-0000000-0884 - Diskretni matematički modeli u kemiji (Damir Vukičević, )

Ustanove
Građevinski fakultet, Zagreb

Časopis indeksira:


  • Scopus


Uključenost u ostale bibliografske baze podataka:


  • MathSciNet