20.500.12556/DKUM-51561 On integer domination in graphs and Vizing-like problems O celoštevilski dominaciji v grafih in problemih Vizingovega tipa Nadaljujemo študij ▫${k}$▫-dominantnih funkcij v grafih (ali, kot bomo tudi rekli, celoštevilske dominacije), ki so jo začeli Domke, Hedetniemi, Laskar in Fricke. Za celo število ▫$k ge 1$▫ je funkcija ▫$f: V(G) to {0,1,...,k}$▫, definirana na točkah grafa ▫$G$▫, ▫${k}$▫-dominantna funkcija, če je vsota funkcijskih vrednosti na vsaki zaprti okolici vsaj ▫$k$▫. Teža ▫${k}$▫-dominantne funkcije je vsota funkcijskih vrednosti po vseh točkah. ▫${k}$▫-dominantno število grafa ▫$G$▫ je najmanjša teža ▫${k}$▫-dominantne funkcije na ▫$G$▫. Obravnavamo ▫${k}$▫-dominantno število kartezičnega produkta grafov, predvsem probleme povezane s slavno Vizingovo domnevo. Študirana je tudi povezava med ▫${k}$▫-dominantnim številom in drugimi tipi dominacijskih parametrov. We continue the study of ▫${k}$▫-dominating functions in graphs (or integer domination as we shall also say) started by Domke, Hedetniemi, Laskar, and Fricke. For ▫$k ge 1$▫ an integer, a function ▫$f: V (G) to {0,1,...,k}$▫ defined on the vertices of a graph ▫$G$▫ is called a ▫${k}$▫-dominating function if the sum of its function values over any closed neighborhood is at least k. ▫$T$▫he weight of a ▫${k}$▫-dominating function is the sum of its function values over all vertices. The ▫${k}$▫-domination number of ▫$G$▫ is the minimum weightof a ▫${k}$▫-dominating function of ▫$G$▫. We study the ▫${k}$▫-domination number on the Cartesian product of graphs, mostly on problems related to the famous Vizing¡ s conjecture. A connection between the ▫${k}$▫-domination number and other domination type parameters is also studied. matematika teorija grafov ▫${k}$▫-dominantna funkcija celoštevilska dominacija Vizingova domneva kartezični produkt grafov mathematics graph theory ▫${k}$▫-dominating function integer domination Vizing's conjecture Cartesian product true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 14:55:11 2015-07-10 14:55:11 2022-05-30 03:06:23 2019-07-11 07:22:18 2006 0 0 str.1317-1328 no. 5 Vol. 10 2006 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 13412872 14099545 1027-5487 URN:SI:UM:DK:0SE3XNYN http://www.math.nthu.edu.tw/~tjm/myweb/FrameConAbs.htm 1 https://dk.um.si/Dokument.php?lang=slv&id=76121 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0