INTEGER DOMINATION INVARIANTS ON GRAPHS

Naj bo Y podmnožica množice celih števil in G = (V,,E) graf. Funkcija, ki vsakemu vozlišču priredi neko vrednost iz množice Y, tako da je seštevek vrednosti v soseščini vsakega vozlišča vsaj 1, se imenuje celoštevilska dominacijska funkcija grafa G. Vrednost celoštevilske dominacijske funkcije v poljubni podmnožici S množice V definiramo kot seštevek vrednosti v vsakem vozlišču iz S. Teža celoštevilske dominacijske funkcije je vrednost funkcije v množici vozlišč V. Poiskati želimo po teži najmanjšo celoštevilsko dominacijsko funkcijo grafa G. V tem delu so predstavljene variacije različnih celoštevilskih dominacij, kot so {k}-dominacija, k-kratna dominacija, predznačena dominacija in minus dominacija, ki jih obravnavamo na razredih grafov kot so poti, cikli, pahljače, kolesa, ponve in trampolini. Podan je algoritem, ki v linearnem času reši problem L-dominacije na strogo tetivnih grafih. Prav tako je podana časovna zahtevnost izračuna naštetih celoštevilskih dominacijskih invariant za razrede dualno tetivnih, dvojno tetivnih in ravninskih grafov. Na koncu je na podoben način predstavljena 2-mavrična dominacija. Let Y be a set of integers. An integer dominating function of graph G = (V,,E) is a function that sets a value from Y to every vertex from V in such way that sum of values from neighbourhood of every vertex is at least 1. Let S be a subset of V. The value of an integer dominating function in S is defined as the sum of its values over vertices from S. The weight of integer dominating function is its value in V. The goal is to find a minimum weight integer dominating function of graph G. In this work we present the variation of integer domination such as {k}-domination, k-tuple domination, signed domination, and minus domination numbers which we study on classes of graphs such as paths, cycles, fans, wheels, pans and suns. We give the algorithm that solves L-domination in linear time on strongly chordal graphs. We also give complexity results for the mentioned integer domination invariants on dually chordal, doubly chordal, and planar graphs. At the end a 2-rainbow domination is presented in a similar way.