Nekateri metrični in kromatični koncepti nad grafovskimi produkti : doktorska disertacija
Jerebic, Janja
V tem delu preučujemo lastnosti krepke izometrične dimenzije grafov in jo primerjamo s sosednostno dimenzijo. Slednjo so neodvisno in v različnih kontekstih predstavili Dewdney [16] ter Poljak in ...Pultr [47]. Posebej obravnavamo grafe premera dva, pri katerih ti dve dimenziji sovpadata. Pokažemo, kako se problem iskanja krepke izometrične dimenzije takih grafov prevede na problem pokritja njihovih komplementov s polnimi dvodelnimi podgrafi. V [21] sta Fitzpatrick in Nowakowski vprašala, ali obstaja graf G, katerega dimenzija je večja od ▫$\lceil \frac{V(G)}{2}$▫. S pomočjo zgoraj omenjenega pristopa konstruiramo take grafe in s tem odgovorimo na zastavljeno vprašanje. Natančno določimo dimenzijo Petersenovega grafa, dimenzije grafov ▫$C_{n}$▫ za ▫$n \geq, \ge 5$▫ ter dimenzije nekaterih grafov ▫$P(n, k)$▫, kjer ▫$P(n, k)$▫ označuje posplošene Petersenove grafe. Primer grafov s premerom dva so tudi prizme nad polnimi grafi. Pri določanju njihove dimenzije, predvsem spodnje meje, nam v veliki meri pomaga Spernerjev izrek. Dobljeni rezultat nato posplošimo na grafe ▫$P_m \cube K_n$▫ in določimo zgornjo mejo dimenzije za Hammingove grafe ▫$K_n /cube K_m$▫. V nadaljevanju preučujemo lastnosti razdalj no uravnoteženih grafov in jih pri danem premeru karakteriziramo. V nadaljevanju pokažemo, da lokalne operacije na grafu razdalj ne uravnoteženosti v večini primerov ne ohranjajo. Za omenjeno lastnost preverimo še, kateri izmed standardnih grafovskih produktov jo ohranjajo. Poleg zgoraj naštetih metričnih lastnosti grafov se podrobno ukvarjamo tudi z grafovskimi invariantami, predvsem z razlikovalnim in razlikovalnim kromatičnim številom. Najprej obravnavamo kartezični produkt poljubnih tujih si grafov in se kasneje omejimo na grafe ▫$K_k \cube K_n$▫. Definiramo po stolpcih invariantne množice, dokažemo lemo o zamenjavi in s pomočjo vsega naštetega natančno določimo razlikovalno število grafov ▫$K_k \cube K_n$▫ ter podamo algoritem za izračun tega števila. Fisher in Isaak [20] sta se prav tako lotila tega problema, vendar z nekoliko drugačnim pristopom. Zato oba pristopa in dobljenerezultate primerjamo. Za konec pokažemo še, da sta za skoraj vse grafe ▫$K_k \cube K_n$▫ razlikovalno kromatično in kromatično število enaki.
Type of material - dissertation
; adult, serious
Publication and manufacture - [S. l. : J. Jerebic], 2008
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.
