Dominating direct products of graphsBrešar, Boštjan (Avtor) Klavžar, Sandi (Avtor) Rall, Douglas F. (Avtor) matematikateorija grafovdominacijadominacija v parihgornja dominacijakartezični produkt grafovmathematicsgraph theorydominationpaired-dominationupper dominationdirect productDokazana 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 3gamma(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.20072015-07-10 14:57:22Delo ni kategorizirano51595sl