| Title: | Nekatere s pakiranji povezane lastnosti grafov |
|---|
| Authors: | ID Božović, Dragana (Author)
ID Peterin, Iztok (Mentor) More about this mentor...  |
|---|
| Files: |  DOK_Bozovic_Dragana_2020.pdf (753,30 KB)
MD5: 36963E8CFCD8575BFE79D14BA56455C1
PID: 20.500.12556/dkum/62090e91-73f5-4664-81e7-fbe988c419ce
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Doctoral dissertation |
|---|
| Typology: | 2.08 - Doctoral Dissertation |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | 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 |
|---|
| Place of publishing: | Maribor |
|---|
| Publisher: | [D. Božović] |
|---|
| Year of publishing: | 2020 |
|---|
| PID: | 20.500.12556/DKUM-76594 |
|---|
| UDC: | 519.17(043.3) |
|---|
| COBISS.SI-ID: | 39788035 |
|---|
| NUK URN: | URN:SI:UM:DK:GXMBZODT |
|---|
| Publication date in DKUM: | 27.11.2020 |
|---|
| Views: | 1798 |
|---|
| Downloads: | 223 |
|---|
| Metadata: |    |
|---|
| Categories: | FNM
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
