Nekatere s pakiranji povezane lastnosti grafov

Božović, Dragana

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Nekatere s pakiranji povezane lastnosti grafov
Avtorji:	ID Božović, Dragana (Avtor) ID Peterin, Iztok (Mentor) Več o mentorju...
Datoteke:	DOK_Bozovic_Dragana_2020.pdf (753,30 KB) MD5: 36963E8CFCD8575BFE79D14BA56455C1 PID: 20.500.12556/dkum/62090e91-73f5-4664-81e7-fbe988c419ce
Jezik:	Slovenski jezik
Vrsta gradiva:	Doktorsko delo/naloga
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
Opis:	V disertaciji se ukvarjamo z različnimi problemi, povezanimi s pakiranji. Disertacija je sestavljena iz štirih delov. Prvi del je namenjen grafom, ki imajo enolično pakirno množico največje moči. Najprej predstavimo nekatere lastnosti teh grafov. Nato podamo še dve karakterizaciji dreves z enolično pakirno množico. V drugem delu vpeljemo pojem dimenzije incidenčnosti, ki je neposredno povezana z 2-pakirnim številom grafa, in določimo formulo za njen izračun. Dokažemo, da je problem iskanja incidenčne dimenzije grafa v splošnem NP-poln. Tretji del namenimo pakirnemu kromatičnemu številu leksikografskega produkta grafov. Določimo njegovo spodnjo in zgornjo mejo ter izboljšano zgornjo mejo za primer, ko je prvi faktor v produktu izomorfen poti. V zadnjem delu se posvetimo učinkoviti odprti dominaciji produktov digrafov. Okarakteriziramo učinkovito odprto dominirane direktne in leksikografske produkte digrafov. Pri kartezičnem produktu okarakteriziramo tiste, kjer je prvi faktor usmerjena pot, usmerjen cikel ali zvezda z enim izvorom. Predstavimo tudi karakterizacijo učinkovito odprto dominiranega krepkega produkta, katerega temeljni graf obeh faktorjev je monocikličen graf.
Ključne besede:	pakirna množica, enolično največje pakiranje, dimenzija incidenčnosti, generator incidenčnosti, pakirno kromatično število, leksikografski produkt grafov, učinkovita odprta dominacija, usmerjeni grafi, produkti usmerjenih grafov
Kraj izida:	Maribor
Založnik:	[D. Božović]
Leto izida:	2020
PID:	20.500.12556/DKUM-76594
UDK:	519.17(043.3)
COBISS.SI-ID:	39788035
NUK URN:	URN:SI:UM:DK:GXMBZODT
Datum objave v DKUM:	27.11.2020
Število ogledov:	1563
Število prenosov:	195
Metapodatki:
Področja:	FNM
:	BOŽOVIĆ, Dragana, 2020, Nekatere s pakiranji povezane lastnosti grafov [na spletu]. Doktorska disertacija. Maribor : D. Božović. [Dostopano 15 marec 2025]. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=76594 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Podobna dela iz repozitorija:

Podobna dela iz ostalih repozitorijev:

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

Licence

Licenca:	CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna

Povezava:	http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:	Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Začetek licenciranja:	12.06.2020

Sekundarni jezik

Jezik:	Angleški jezik
Naslov:	Some graph properties related to packings
Opis:	In this dissertation, different problems related to packings are presented. The dissertation consists of four parts. In the first part, we focus on graphs with the unique packing of maximum cardinality. We first present several general properties for such graphs. Later two characterizations of trees with the unique maximum packing are presented. The second part introduces the concept of incidence dimension, which is directly related to the packing of a graph. We determine the formula for its calculation and prove that the problem of finding the incidence dimension of a graph is NP-complete in the general case. The third part is devoted to the packing chromatic number of the lexicographic product of graphs. Its lower and upper bounds are determined. The improved upper bound for the case where the first factor in the product is isomorphic to a path on $n$ vertices is also presented. The last section deals with the efficient open domination of digraph products. We characterize the efficient open domination direct and lexicographic products of digraphs. Among Cartesian products, those whose first factor is a directed path, a directed cycle, or a single-source star are characterized. Characterization of the efficient open domination strong product digraphs for which the underlying graph of both factors is unicyclic is also presented.
Ključne besede:	packing set, unique maximum packing, incidence dimension, incidence generator, packing chromatic number, lexicographic product of graphs, efficient open domination, digraphs, products of digraphs

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj