-
Kartezični produkti grafov in ekspanzije : doktorska disertacijaBrešar, BoštjanObravnavamo problem strukture S-pragrafov, to je grafov, ki se ne dajo predstaviti kot netrivialni podgrafi kartezičnega produkta netrivialnih grafov. Dokažemo karakterizacijo S-pragrafov s ... povezanostjo 2 in vpeljemo pojem ekstenzije, s katero iz danega S-pragrafa dobimo nov S-pragraf. Dokažemo karakterizacijo S-pragrafov kot grafov, ki jih lahko dobimo z zaporedjem ekstenzuj iz enostavnih S-pragrafov. Slednji predstavljajo razmeroma majhen podrazred S-pragrafov. V poglavju o Vizingovi domnevi, ki trdi, da je dominantno število kartezičnega produkta grafov večje ali kvečjemu enako produktu dominantnih števil faktorjev, dokažemo, da le-ta drži le v primeru, ko imata faktorja dominantno število 3. Poleg tega, poglavje vsebuje kratek dokaz rezultata analognega Vizingovi domnevi, kjer je eno od dominantnih števil faktorjev zamenjamo z deljenim dominantnim številom. Najobsežnejše poglavje je namenjeno izometričnim podgrafom Hammingovih grafov ter posameznim podrazredom teh grafov. Z uporabo relacije ▫$\Theta$▫ na množici povezav dokažemo karakterizacije delnih Hammingovih grafov, ki predstavljajo posplošitev Winklerjeve karakterizacije delnih kock. Spoznamo nekaj lastnosti ekspanzij na delnih Hammingovih grafih in uvedemo nov podrazred teh grafov, t.i. semikvazimedianske grafe. Raziščemo odnos le-teh v razmerju s kvazimedianskimi in delnimi Hammingovimi grafi ter dokažemo karakterizacijo kvazimedianskih grafov kot delnih Hammingovih grafov z uporabo prepovedanih podgrafov in enakostjo posameznih relacij na množici povezav grafa. Z uporabo določene vrste povezane ekspanzije dokažemo karakterizacijo semimedianskih grafov. Končamo še z dvema karakterizacijama kvazimedianskih grafov, ki uporabljata štirikotniško lastnost. Zadnje poglavjeje namenjeno direktni ekspanziji, ki jo poraja direktni produkt grafov. Dokažemo karakterizacijo grafov, za katere je vsaka direktna ekspanzija nepovezan graf ter grafov, za katere je vsaka netrivialna direktna ekspanzija povezan graf. V prvem primeru dobimo natanko drevesa, v drugem pa je rezultat povezan z neodvisnimi presečnimi množicami ter določenimi metričnimi lastnostmi dvodelnih podgrafov danega grafa. Nazadnje obravnavamo ohranitev povezanosti grafov ob zaporedni uporabi direktne ekspanzije in pokažemo, da je za veliko razredov grafov možno neskončno zaporedje direktnih ekspanzij, v katerem so vsi grafi povezani.Vrsta gradiva - disertacijaZaložništvo in izdelava - Maribor : [B. Brešar], 2000Jezik - slovenskiCOBISS.SI-ID - 1686060
Avtor
Brešar, Boštjan
Drugi avtorji
Klavžar, Sandi |
Vukman, Joso
Teme
mathematics |
graph theory |
distance |
Cartesian product |
isometric subgraph |
convexity |
gatedness |
Hamming graph |
hypercube |
quasi-median graph |
median graph |
S-prime graph |
domination |
independent set |
expansion |
direct product |
connectivity |
teorija grafov |
graf |
razdalja |
kartezični produkt |
izometrični podgraf |
konveksnost |
zastraženost |
Hammingov graf |
hiperkocka |
kvazimedianski graf |
medianski graf |
pragraf |
dominacija |
neodvisna množica |
ekspanzija |
direktni produkt |
povezanost
Knjižnica | Signatura – lokacija, inventarna št. ... | Status izvoda |
---|---|---|
Narodna in univerzitetna knjižnica, Ljubljana | GS II 523135 glavno skladišče | prosto - za čitalnico |
FMF in IMFM, Matematična knjižnica, Ljubljana | Skladišče-Jadranska 19 11024/5 |
prosto - za čitalnico |
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Brešar, Boštjan | 17005 |
Klavžar, Sandi | 05949 |
Vukman, Joso | 04310 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.