20.500.12556/DKUM-10406 CELOŠTEVILSKE DOMINACIJSKE INVARIANTE NA GRAFIH 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. celoštevilska dominacija k-kratna dominacija predznačena dominacija minus dominacija {k}-dominacija 2-mavrična dominacija tetivni grafi dualno tetivni grafi dvojno tetivni grafi strogo tetivni grafi integer domination k-tuple domination signed domination minus domination {k}-domination 2-rainbow domination chordal graphs dually chordal graphs doubly chordal graphs strongly chordal graphs true true false [L. Komovec] Slovenski jezik Angleški jezik Diplomsko delo 2009-05-13 10:32:55 2009-06-17 13:12:15 2022-04-11 16:15:09 2022-04-16 03:25:39 2009 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 16946440 URN:SI:UM:DK:ZWDXKEUX UNI_Komovec_Luka_2009.pdf UNI_Komovec_Luka_2009.pdf 1 7E3466DB81BD1165BCD4DA9A9499F507 9e8e2ab55cde19c90d8149f9d74d9db0a6a6bcbdbb12fbc332d54de2dc3cbbfb d1dd8e8c-7c02-11eb-bb7a-00155d0001ca 20.500.12556/dkum/fe0fef5d-2538-49d9-a751-d3bb9e7253bc https://dk.um.si/Dokument.php?lang=slv&id=8489 Fakulteta za naravoslovje in matematiko 0 0 0