Embeddings of snarks into closed surfaces : doctoral thesis
Vodopivec, Andrej, 1978-
V disertaciji obravnavamo vložitve kubičnih grafov razreda 2. Kubični grafi razreda 2 z nekaj dodatnimi pogoji na povezanost so znani kot snarki. Motivacija za študij vložitev snarkov prihaja iz ...poskusov dokaza izreka štirih barv. Izrek štirih barv trdi, da je mogoče točke vsakega enostavenega ravninskega grafa pobarvati s štirimi barvami tako, da so sosednje točke pobarvane z različnima barvama. Izrek je ekvivalenten trditvi, da je mogoče povezave vsakega enostavnega 3-povezanega kubičnega grafa povarvati s tremi barvami tako, da sta dve sosednji povezavi pobarvani z različnima barvama. Povezave enostavnega kubičnega grafa lahko pobarvamo s tremi ali pa s štirimi barvami. Kubični grafi, katerih povezave ne moremo pobarvati s tremi barvami, so grafi razreda 2. Izrek štirih barv pravi, da 3-povezani kubični grafi razreda 2 niso ravninski. Ena izmed posplošitev izreka štirih barv je trditev,da so kubični grafi, ki imajo poliedrsko vložitev v kako orientabilno ploskev, razreda 1. Posplošitev je znana kot Grünbaumova hipoteza in je bila podana leta 1969 in je po skoraj 40 letih še vedno odprta. Študij začnemo s študijem znanih družin snarkov. Določimo orientabilni in neorientailni rod cvetnih snarkov in Goldbergovih snarkov. Potem študiramo rod 4-vsote grafov, posebej se posvetimo rodu 4-vsot Petersenovega grafa. Nato študiramo poliedrske vložitve znanih družin snarkov. Pokažemo, da so kratki cikli v kubičnih grafih lica v poliedrskih vložitvah. Pokažemo, da cvetni snarki nimajo poliedrskih vložitev niti v orientabilne niti v neorientabilne ploskve in da Goldbergovi snarki nimajo poliedrskih vložitev v orientabilne ploskve. Za vsako neorientabilno ploskev ▫$N$▫ konstruiramo snark, ki ima poliedrsko vložitev v ▫$N$▫. V zadnjem poglavju študiramo poliedrske vložitve grafov dobljenih s superpozicijo. Za Kocholove snarke pokažemo, da nimajo poliedrskih vložitev v orientabilne ploskve. Definiramo degeneriranost grafa kot mero kako daleč je kubičen graf od tega, da ima poliedrsko vložitev. V primeru, da Grünbaumova hipoteza drži, pokažemo povezavo med degeneriranostjo in odpornostjo grafa. Odpornost meri, kako daleč je kubičen graf od tega, da ima 3-barvanje povezav. Pokažemo, da so v primeru, da Grünbaumova hipoteza drži, kubični grafi, ki so daleč od tega, da imajo 3-barvanje povezav, tudi daleč od tega, da imajo poliedrske vložitve.
Type of material - dissertation
Publication and manufacture - Ljubljana : [A. Vodopivec], 2007
Central Technological Library of the University of Ljubljana
52047/1735 Skladišče IN: 320080065
available - outside loan, loan period: 14 days
FMF, Mathematical Library, Lj.
Skladišče-Jadranska 21
10921/94
available - reading room
Shelf entry
Adding material to shelf was successful.
Adding material to shelf failed.
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.
