| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 25
First pagePrevious page123Next pageLast page
1.
2.
3.
IZREKI NORDHAUS-GADDUMOVEGA TIPA ZA NEKATERE KROMATIČNE INVARIANTE
Eva Iršič, 2012, undergraduate thesis

Abstract: Diplomska naloga obravnava izreke Nordhaus-Gaddumovega tipa za nekatere kromatične invariante. Na začetku predstavimo osnovne pojme teorije grafov, ki so potrebni za razumeva- nje nadaljne snovi. V nalogo so vključene nekatere kromatične invariante, kot so kromatično število, seznamsko kromatično število ter akromatično in psevdoakromatično število. Konec pa vključuje število mavrične povezanosti. Za vsoto in produkt kromatičnega števila grafa in njegovega komplementa določimo spodnjo in zgornjo mejo, prav tako določimo zgornjo mejo za vsoto seznamskega kromatičnega števila grafa in njegovega komplementa. Preverimo neenakosti, ki veljajo za akromatično in psevdoakromatično število in nazadnje določimo spodnjo in zgornjo mejo za vsoto števil mavrične povezanosti grafa in njegovega komplementa.
Keywords: kromatično število, akromatično število, psevdoakromatično število, seznamsko kromatično število, število mavrične povezanosti
Published: 02.08.2012; Views: 1094; Downloads: 81
.pdf Full text (518,78 KB)

4.
Nekatere posplošitve grafov Sierpińskega
Andreja Šereg, 2013, undergraduate thesis

Abstract: V diplomskem delu so predstavljeni grafi Sierpińskijevega tipa, in sicer grafi Sierpińskega S(n, k), grafi trikotnikov Sierpińskega S_n, regularni grafi Sierpińskega S^+(n, k) in S^++(n, k) ter posplošeni grafi trikotnikov Sierpińskega S[n, k]. Prikazane so natančne risbe grafov S(n, k), S^+(n, k) in S^++(n, k). Za S^+(n, k) in S^++(n, k) je dokazano, da so te risbe optimalne. Določeno je število po povezavah disjunktnih Hamiltonovih poti in Hamiltonovih ciklov v grafih S(n, k), S^+(n, k) in S^++(n, k). Dokazano je, da so grafi S[n, k] Hamiltonovi. Raziskana je vozliščna linearna pogozdenost grafov S(n, k), S^+(n, k), S^++(n, k) in S[n, k]. Podano je še {P_r}-prosto kromatično število grafov S_n, S(n, k), S^+(n, k) in S^++(n, k), za r ∈ {3, 4}.
Keywords: graf Sierpińskega, graf trikotnikov Sierpińskega, regularni graf Sierpińskega, posplošeni graf trikotnikov Sierpińskega, prekrižno število, hamiltonskost, t-barvanje poti, vozliščna linearna pogozdenost, {P_r}-prosto kromatično število
Published: 19.09.2013; Views: 988; Downloads: 81
.pdf Full text (5,07 MB)

5.
Celotno kromatično število regularnih grafov z visoko stopnjo vozlišč
Lidija Prašnički, 2015, master's thesis

Abstract: V magistrskem delu je obravnavano celotno kromatično število regularnih grafov z visoko stopnjo vozlišč. Celotno kromatično število grafa je najmanjše število barv, ki jih potrebujemo, da pobarvamo vozlišča in povezave grafa tako, da sosednja ali incidentna elementa nimata enakih barv. Behzad-Vizingova domneva nam poda spodnjo in zgornjo mejo za celotno kromatično število. V magistrskem delu dokažemo, da regularni grafi, ki izpolnjujejo določene pogoje povezane s stopnjo grafa, zadoščajo tej domnevi. V prvem poglavju so definirani nekateri pojmi in navedeni pomembni rezultati iz teorije grafov, ki jih potrebujemo v nadaljevanju. V drugem poglavju so obravnavani grafi sodega reda z visoko stopnjo vozlišč. Najprej so podani pomembni rezultati za poljubne grafe, potem pa je v drugem podpoglavju dokazano, da regularni graf sodega reda z visoko stopnjo vozlišč, ki izpolnjuje določen pogoj, zadošča Behzad-Vizingovi domnevi. V tretjem poglavju so podobno obravnavani tudi poljubni in regularni grafi lihega reda z visoko stopnjo vozlišč.
Keywords: celotno kromatično število, regularni graf, prirejanje grafa
Published: 23.03.2015; Views: 873; Downloads: 91
.pdf Full text (744,11 KB)

6.
Locirajoče kromatično število grafa
Karmen Unuk, 2015, bachelor thesis/paper

Abstract: V diplomskem delu je obravnavano locirajoče kromatično število grafa. Za barvanje $c$ povezanega grafa $G$ naj bo $pi=(C_1,C_2, ldots ,C_k)$ urejena particija množice vozlišč $V(G)$ glede na barvanje $c$. Za vozlišče $v$ grafa $G$ je barvna koda $c_{pi}(v)$ vozlišča $v$ urejena $k$-terica $(d(v,C_1),d(v,C_2), ldots ,d(v,C_k))$, kjer je $d(v,C_i)=min{d(v,x)|x in C_i}$, za $i in {1, ldots ,k}$. Če imata različni vozlišči različni barvni kodi, potem $c$ imenujemo locirajoče barvanje. Locirajoče kromatično število, $chi_L(G)$, je najmanjše število barv, potrebnih za locirajoče barvanje grafa $G$. Meje za locirajoče kromatično število povezanega grafa so ugotovljene s stališča njegovega reda in premera. Določeni so vsi povezani grafi reda $n geq 3$ z locirajočim kromatičnim številom $n$. Pokazano je, da za vsak par naravnih števil $a,b geq 2$ obstaja povezan graf s kromatičnim številom $a$ in locirajočim kromatičnim številom $b$. Določeno je locirajoče kromatično število nekaterih znanih grafov. Posebej je predstavljeno locirajoče kromatično število dreves.
Keywords: locirajoče barvanje, locirajoče kromatično število
Published: 21.04.2015; Views: 560; Downloads: 74
.pdf Full text (1,00 MB)

7.
The distinguishing chromatic number of Cartesian products of two complete graphs
Janja Jerebic, Sandi Klavžar, 2008

Abstract: Označitev grafa ▫$G$▫ je razlikovalna, če jo ohranja le trivialni avtomorfizem grafa ▫$G$▫. Razlikovalno kromatično število grafa ▫$G$▫ je najmanjše naravno število, za katero obstaja razlikovalna označitev grafa, ki je hkrati tudi dobro barvanje. Za vse ▫$k$▫ in ▫$n$▫ je določeno razlikovalno kromatično število kartezičnih produktov ▫$K_kBox K_n$▫. V večini primerov je enako kromatičnemu številu, kar med drugim odgovori na vprašanje Choia, Hartkeja and Kaula, ali obstajajo še kakšni drugi grafi, za katere velja enakost.
Keywords: teorija grafov, razlikovalno kromatično število, grafovski avtomorfizem, kartezični produkt grafov, graph theory, distinguishing chromatic number, graph automorphism, Cartesian product of graphs
Published: 10.07.2015; Views: 396; Downloads: 49
URL Link to full text

8.
Chromatic numbers of strong product of odd cycles
Janez Žerovnik, 2002, published scientific conference contribution

Abstract: The problem of determining the chromatic numbers of the strong product of cycles is considered. A construction is given proving ▫$chi(G) = 2^p + 1$▫ for a product of ▫$p$▫ odd cycles of lengths at least ▫$2^p + 1$▫. Several consequences are discussed. In particular it is proved that the strong product of ▫$p$▫ factors has chromatic number at most ▫$2^p + 1$▫ provided that each factor admits the homomorphism to sufficiently long odd cycle ▫$C_{m_i}, ; m_i ge 2^p + 1$▫.
Keywords: matematika, teorija grafov, krepki produkt grafov, kromatično število, lih cikel, minimalna neodvisna dominantna množica, mathematics, graph theory, strong product, chromatic number, odd cycle, minimal independent dominating set
Published: 10.07.2015; Views: 522; Downloads: 49
URL Link to full text

9.
Behzad-Vizing conjecture and Cartesian-product graphs
Blaž Zmazek, Janez Žerovnik, 2004, published scientific conference contribution

Abstract: Dokazali smo naslednji izrek: Če Behzad-Vizingova domneva velja za grafa ▫$G$▫ in ▫$H$▫, potem velja tudi za kartezični produkt ▫$G Box H$▫.
Keywords: matematika, teorija grafov, kartezični produkt grafov, kromatično število, popolno kromatično število, Vizingova domneva, mathematics, graph theory, Cartesian graph product, chromatic number, total chromatic number, Vizing conjecture
Published: 10.07.2015; Views: 549; Downloads: 54
URL Link to full text

10.
Search done in 0.16 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica