crta
Hrvatska znanstvena Sekcija img
bibliografija
3 gif
 Naslovna
 O projektu
 FAQ
 Kontakt
4 gif
Pregledavanje radova
Jednostavno pretraživanje
Napredno pretraživanje
Skupni podaci
Upis novih radova
Upute
Ispravci prijavljenih radova
Ostale bibliografije
Slični projekti
 Bibliografske baze podataka

Pregled bibliografske jedinice broj: 328539

Časopis

Autori: Vukičević, Damir; Došlić, Tomislav
Naslov: Global forcing number of grid graphs
( Global forcing number of grid graphs )
Izvornik: Australasian Journal of Combinatorics (1034-4942) 38 (2007); 47-62
Vrsta rada: članak
Ključne riječi: global forcing number; grid graph
( 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.
Projekt / tema: 037-0000000-2779, 177-0000000-0884
Izvorni jezik: eng
Rad je indeksiran u
bazama podataka:
Scopus
Kategorija: Znanstveni
Znanstvena područja:
Matematika
URL cjelovitog teksta:
Google Scholar: Global forcing number of grid graphs
Upisao u CROSBI: Tomislav Došlić (), 11. Tra. 2008. u 14:14 sati



  Verzija za printanje   za tiskati


upomoc
foot_4