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\u27s 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$▫