Dominating direct products of graphs

Boštjan Brešar (Avtor), Sandi Klavžar (Avtor), Douglas F. Rall (Avtor)

Povzetek

Dokazana je zgornja meja za dominantno število direktnega produkta grafov. V posebnem primeru iz meje sledi, da za poljubna grafa ▫$G$▫ in ▫$H$▫ velja ▫$\gamma (G \times H) \le 3\gamma(G)\gamma(H)$▫. Konstruirani so grafi s poljubno velikimi dominantnimi števili, za katere je ta meja dosežena. Za gornje dominantno število dokažemo, da velja ▫$\Gamma(G \times H) \ge \Gamma(G)\Gamma(H)$▫, s čimer je potrjena domneva iz [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Nazadnje za dominacijo v parih direktnih produktov dokažemo, da za poljubna grafa ▫$G$▫ in ▫$H$▫ velja ▫$\gamma_{\rm{pr}}(G \times H) \le \gamma_{\rm{pr}} (G)\gamma_{\rm{pr}}(H)$▫. Predstavimo tudi neskončne družine grafov, pri katerih je ta meja dosežena.

Ključne besede

matematika;teorija grafov;dominacija;dominacija v parih;gornja dominacija;kartezični produkt grafov;mathematics;graph theory;domination;paired-domination;upper domination;direct product;

Podatki

Jezik:	Angleški jezik
Leto izida:	2007
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	14286937
ISSN:	0012-365X
Št. ogledov:	37
Št. prenosov:	22
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Dominiranje direktnih produktov grafov
Sekundarni povzetek:	An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs ▫$G$▫ and ▫$H$▫, ▫$\gamma (G \times H) \le 3\gamma(G)\gamma(H)$▫. Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that ▫$\Gamma(G \times H) \ge \Gamma(G)\Gamma(H)$▫, thus confirming a conjecture from [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Finally, for paired-domination of direct products we prove that ▫$\gamma_{\rm{pr}}(G \times H) \le \gamma_{\rm{pr}}(G)\gamma_{\rm{pr}}(H)$▫ for arbitrary graphs ▫$G$▫ and ▫$H$▫, and also present some infinite families of graphs that attain this bound.
Sekundarne ključne besede:	matematika;teorija grafov;dominacija;dominacija v parih;gornja dominacija;kartezični produkt grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1636-1642
Letnik:	ǂVol. ǂ307
Zvezek:	ǂiss. ǂ13
Čas izdaje:	2007
ID:	1473063