-
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.Type of material - dissertationPublication and manufacture - Maribor : [B. Brešar], 2000Language - slovenianCOBISS.SI-ID - 1686060
Author
Brešar, Boštjan
Other authors
Klavžar, Sandi |
Vukman, Joso
Topics
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
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Library | Call number – location, accession no. ... | Copy status |
---|---|---|
Miklošič Library FPNM, Maribor | D DIS 51 BREŠAR B. Kartezični IN: 120013495 |
available - reading room |
University of Maribor Library | Skladišče II 50131 | available - reading room |
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
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 |
---|---|
Brešar, Boštjan | 17005 |
Klavžar, Sandi | 05949 |
Vukman, Joso | 04310 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.