| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graph
Avtorji:Šparl, Petra (Avtor)
Žerovnik, Janez (Avtor)
Datoteke:URL http://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=68552
 
Jezik:Angleški jezik
Vrsta gradiva:Delo ni kategorizirano (r6)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FOV - Fakulteta za organizacijske vede
Opis:Problem odločanja ali obstaja homomorfizem iz poljubnega grafa ▫$G$▫ v dani graf ▫$H$▫ je bil že večkrat proučevan in se je izkazal za zelo težkega. Hell in Nešetril sta dokazala, da je odločitveni problem NP-poln, če ▫$H$▫ ni dvodelen graf. V članku je obravnavan poseben problem, kjer je ▫$G$▫ poljuben heksagonalen graf brez trikotnikov, ▫$H$▫ pa Kneserjev graf ali njegov inducirani podgraf. Podana je esplicitna konstrukcija, ki dokazuje obstoj homomorfizma iz poljubnega heksagonalnega grafa brez trikotnikov v Petersenov graf brez ene točke.
Ključne besede:matematika, teorija grafov, homomorfizem, H-barvanje, heksagonalen graf brez trikotnikov, mathematics, teorija grafov, homomorphism, H-coloring, triangle-free hexagonal graph
Leto izida:2009
Št. strani:str. 391-398
Številčenje:Vol. 14, no. 2
UDK:519.17
COBISS_ID:15524441 Povezava se odpre v novem oknu
ISSN pri članku:1331-0623
NUK URN:URN:SI:UM:DK:WOPETDQH
Število ogledov:407
Število prenosov:10
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Mathematical communications
Skrajšan naslov:Math. commun., Croat. Math. Soc., Divis. Osijek
Založnik:Croatian Mathematical Society - Division Osijek
ISSN:1331-0623
COBISS.SI-ID:8266073 Novo okno

Sekundarni jezik

Jezik:Neznan jezik
Naslov:Ekspliciten homomorfizem heksagonalnih grafov v Petersenov graf brez ene točke
Opis:The problem of deciding whether an arbitrary graph ▫$G$▫ has a homomorphism into agiven graph ▫$H$▫ has been widely studied and has turned out to be very difficult. Hell and Nešetril proved that the decision problem is NP-complete unless ▫$H$▫ is bipartite. We consider a restricted problem where ▫$G$▫ is an arbitrary triangle-free hexagonal graph and ▫$H$▫ is a Kneser graph or its induced subgraph. We give an explicit construction which proves that any triangle-free hexagonal graph has a homomorphism into one-vertex deleted Petersen graph.


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici