On domination numbers of graph bundles

Blaž Zmazek (Avtor), Janez Žerovnik (Avtor)

Povzetek

Let ▫$\gamma(G)$▫ be the domination number of a graph ▫$G$▫. It is shown that for any ▫$k \ge 0$▫ there exists a Cartesian graph bundle ▫$B \Box_\varphi F$▫ such that ▫$\gamma(B \Box_\varphi F) = \gamma(B)\gamma(F) - 2k$▫. The domination numbers of Cartesian bundles of two cycles are determined exactly when the fibre graph is a triangle or a square. A statement similar to Vizing's conjecture on strong graph bundles is shown not to be true by proving the inequality ▫$\gamma(B \boxtimes_\varphi F) \le \gamma(B)\gamma(F)$▫ for strong graph bundles. Examples of graphs ▫$B$▫ and ▫$F$▫ with ▫$\gamma(B \boxtimes_\varphi F) < \gamma(B)\gamma(F)$▫ are given.

Ključne besede

matematika;teorija grafov;kartezični produkt grafov;dominantno število;dominantna množica;grafovski sveženj;mathematics;graph theory;graph bundle;dominating set;domination number;Cartesian product;

Podatki

Jezik:	Angleški jezik
Leto izida:	2005
Tipologija:	0 - Ni določena
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	13826905
ISSN:	1318-4865
Št. ogledov:	1008
Št. prenosov:	85
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarne ključne besede:	matematika;teorija grafov;kartezični produkt grafov;dominantno število;dominantna množica;grafovski sveženj;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1-10
Letnik:	ǂVol. ǂ43
Zvezek:	ǂšt. ǂ998
Čas izdaje:	2005
ID:	66705