20.500.12556/DKUM-51595 Dominating direct products of graphs Dominiranje direktnih produktov grafov 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 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. 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 3gamma(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. matematika teorija grafov dominacija dominacija v parih gornja dominacija kartezični produkt grafov mathematics graph theory domination paired-domination upper domination direct product true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 14:57:22 2015-07-10 14:57:22 2022-05-30 03:06:32 2019-07-11 07:23:12 2007 0 0 str. 1636-1642 iss. 13 Vol. 307 2007 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1118479 14286937 0012-365X URN:SI:UM:DK:6FX9XHHM http://dx.doi.org/10.1016/j.disc.2006.09.013 1 https://dk.um.si/Dokument.php?lang=slv&id=76155 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0