izpis_h1_title_alt

Pakirno kromatično število koron nad potmi in cikli : delo diplomskega seminarja
Robba, Barbara (Avtor), Klavžar, Sandi (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (428,64 KB)

Izvleček
Pakirno kromatično število $\chi_{\pi}(G)$ grafa $G$ je najmanjši $k$, za katerega lahko poiščemo $k$-pakirno barvanje grafa, torej najmanjši $k$, za katerega obstaja taka funkcija $\pi: (G) \to [k]$, da iz $\pi(u) = \pi(v)$ sledi, da je razdalja med $u$ in $v$ večja od $\pi(u)$. Za graf $G$ in $p \ge 1$ definiramo $p$-korono grafa $G$ kot graf, ki ga iz grafa $G$ dobimo tako, da na vsako njegovo vozlišče pripnemo $p$ dodatnih listov (torej vozlišč stopnje ena). Določanje pakirnega kromatičnega števila grafa je v splošnem težek problem, kar v delu nakažemo s tem, da dokažemo, da je 4-pakirno barvanje NP-poln problem. Nato dokažemo izrek o pakirnem kromatičnem številu na poteh in ciklih, zatem pa se omejimo na pakirno kromatično število $p$-koron poti in ciklov.

Jezik:Slovenski jezik
Ključne besede:pakirno barvanje, pakirno kromatično število, korona grafa, pot, cikel
Vrsta gradiva:Delo diplomslega seminarja/zaključno seminarsko delo/naloga (mb14)
Organizacija:FMF - Fakulteta za matematiko in fiziko
Leto izida:2019
UDK:519.1
COBISS.SI-ID:18725465 Povezava se odpre v novem oknu
Število ogledov:53
Število prenosov:15
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
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...

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Packing Chromatic Number of Coronae of Paths and Cycles
Izvleček:
The packing chromatic number $\chi_{\pi}(G)$ of a graph $G$ is the smallest integer $k$ for which a packing k-coloring of graph $G$ can be found, which is the smallest $k$ for which such a function $\pi: (G) \to [k]$ exists, that from $\pi(u) = \pi(v)$ follows that the distance between u and v is greater than $\pi(u)$. For a graph $G$ and $p \ge 1$, a $p$-coronae of the graph $G$ is defined as the graph we obtain graph $G$ by adding p additional leaves (vertices of degree 1) to each vertex on the graph. Determining the packing chromatic number of a graph is a complex problem. In this paper we show this by presenting a proof that 4-packing coloring is an NP-complete problem. Then we prove a theorem on the packing chromatic number of paths and cycles, and afterwards focus on the packing chromatic number of $p$-coronae of paths and cycles.

Ključne besede:packing coloring, packing chromatic number, corona graph, path, cycle

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

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

Nazaj