20.500.12556/DKUM-65351 On Vizing's conjecture O Vizingovi domnevi A dominating set ▫$D$▫ gor a graph ▫$G$▫ is a subset ▫$V(G)$▫ such that any vertex in ▫$V(G)-D$▫ has a neighbor in ▫$D$▫, and a domination number ▫$\gamma(G)$▫ is the size of a minimum dominating set for ▫$G$▫. For the Cartesian product ▫$G \Box H$▫ Vizing's conjecture states that ▫$\gamma(G \Box H) \ge \gamma(G)\gamma(H)$▫ for every pair of graphs ▫$G,H$▫. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when ▫$\gamma(G) = \gamma(H) = 3$▫. Dominirajoča množica ▫$D$▫ grafa ▫$G$▫ je taka podmnožica množice ▫$V(G)$▫, za katero ima vsaka točka iz množice ▫$V(G)-D$▫ kako sosedo v ▫$D$▫; dominantno število ▫$\gamma(G)$▫ pa je velikost najmanjše dominirajoče množice grafa ▫$G$▫. Za kartezični produkt grafov ▫$G \Box H$▫ Vizingova domneva trdi, da je ▫$\gamma(G \Box H) \ge \gamma(G)\gamma(H)$▫, kjer sta ▫$G$▫ in ▫$H$▫ poljubna grafa. V članku vpeljemo nov koncept, ki posploši običajno dominacijo grafov in dokažemo, da domneva drži v promeru, ko je ▫$\gamma(G) = \gamma(H) = 3$▫. mathematics graph theory graph Cartesian product domination number matematika teorija grafov graf kartezični produkt dominantno število true true true Angleški jezik Slovenski jezik Znanstveno delo 2017-03-31 14:20:00 2017-03-31 14:22:24 2022-07-08 03:07:41 2019-07-11 15:15:29 2001 0 0 str. 5-11 št. 1 Letn. 21 2001 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1234-3099 519.17 7487065 11010137 1234-3099 URN:SI:UM:DK:PXU92DXH Discussiones_Mathematicae_Graph_Theory_2001_Bresar_On_Vizing_s_conjecture.pdf Discussiones_Mathematicae_Graph_Theory_2001_Bresar_On_Vizing_s_conjecture.pdf 1 286C4062475D3BCDAD7F938289E2AA70 471f573a9cf3c6665bb7b9a28128b1926c2cff95fdccabd0c68335a94360cb59 0be775b2-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=110429 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1129 1 https://dk.um.si/Dokument.php?lang=slv&id=110428 Fakulteta za kmetijstvo in biosistemske vede 0 0 0