| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:CELOŠTEVILSKE DOMINACIJSKE INVARIANTE NA GRAFIH
Avtorji:Komovec, Luka (Avtor)
Brešar, Boštjan (Mentor) Več o mentorju... Novo okno
Datoteke:.pdf UNI_Komovec_Luka_2009.pdf (501,60 KB)
 
Jezik:Slovenski jezik
Vrsta gradiva:Diplomsko delo (m5)
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
Opis: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.
Ključne besede: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
Leto izida:2009
Založnik:[L. Komovec]
Izvor:Maribor
UDK:51(043.2)
COBISS_ID:16946440 Povezava se odpre v novem oknu
NUK URN:URN:SI:UM:DK:ZWDXKEUX
Število ogledov:1831
Število prenosov:131
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:FNM
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Sekundarni jezik

Jezik:Angleški jezik
Naslov:INTEGER DOMINATION INVARIANTS ON GRAPHS
Opis: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.
Ključne besede: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


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici