Lower bounds for domination and total domination number of direct products graphsMekiš, Gašper (Avtor) matematikateorija grafovdominacijska množicadominacijsko številocelotna dominacijska množicacelotno dominacijsko številodirektni produkt grafovpoln grafmathematicsgraph theorydominating setdomination numbertotal dominating settotal domination numberdirect product graphscomplete graphsAn exact lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: ▫$gamma(times_{i=1}^t K_{n_i} ge t+1$▫, ▫$t ge 3$▫. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: ▫$gamma(G times H) ge gamma(G) + gamma(H) - 1$▫. Infinite families of graphs that attain the bound are presented. For these graphs it also holds ▫$gamma_t(G times H) = gamma(G) + gamma(H) - 1$▫. Some additional parallels with the total domination number are made.20092015-07-10 15:10:05Delo ni kategorizirano51800ISSN: 1318-4865UDK: 519.17OceCobissID: 44310272COBISS_ID: 15246425NUK URN: URN:SI:UM:DK:V19CW8I1sl