-
Embeddings of snarks into closed surfaces : doctoral thesisVodopivec, 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 - dissertationPublication and manufacture - Ljubljana : [A. Vodopivec], 2007Language - english, slovenianCOBISS.SI-ID - 14416985
Author
Vodopivec, Andrej, 1978-
Other authors
Mohar, Bojan
Topics
kromatični indeks |
kubičen graf |
snark |
poliedrska vložitev |
cvetni snark |
Goldbergov snark |
superpozicija |
Kocholov snark |
chromatic index |
cubic graph |
snark |
polyhedral embedding |
flower snark |
Goldberg snark |
superposition |
Kochol snark
Call number – location, accession no. ... |
Copy status | Reservation |
---|---|---|
Skladišče-Jadranska 21 0000010921/0000000094 Skladišče-Jadranska 21 10921/94 |
available - reading room
|
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 |
---|---|
Vodopivec, Andrej, 1978- | 24049 |
Mohar, Bojan | 01931 |
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.