Kartezični produkti grafov in ekspanzije : doktorska disertacija
Brešar, Boštjan
Obravnavamo 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.
Type of material - dissertation
Publication and manufacture - Maribor : [B. Brešar], 2000
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
