Dominating direct products of graphs

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

Abstract

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.

Keywords

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

Data

Language:	English
Year of publishing:	2007
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	14286937
ISSN:	0012-365X
Views:	37
Downloads:	22
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Dominiranje direktnih produktov grafov
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;dominacija;dominacija v parih;gornja dominacija;kartezični produkt grafov;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1636-1642
Volume:	ǂVol. ǂ307
Issue:	ǂiss. ǂ13
Chronology:	2007
ID:	1473063