399 KB49 KB200820252015Althöfer, IngoHaugland, Jan KristianScherer, KarlSchneider, FrankVan Cleemput, Nicoštevilka:2letnik:8str. 337-363COBISSID:17377369ISSN:1855-3966URN:URN:NBN:SI:doc-S061169TenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaalternating degreesalternirajoče stopnjeexhaustive searchheuristic searchhevristično iskanjeizčrpno iskanjeplane graphravninski grafiAlternating plane graphs|A plane graph is called alternating if all adjacent vertices have different degrees, and all neighboring faces as well. Alternating plane graphs were introduced in 2008. This paper presents the previous research on alternating plane graphs. There are two smallest alternating plane graphs, having 17 vertices and 17 faces each. There is no alternating plane graph with 18 vertices, but alternating plane graphs exist for all cardinalities from 19 on. From a small set of initial building blocks, alternating plane graphs can be constructed for all large cardinalities. Many of the small alternating plane graphs have been found with extensive computer help. Theoretical results on alternating plane graphs are included where all degrees have to be from the set ?$\{3,4,5\}$?. In addition, several classes of "weak alternating plane graphs" (with vertices of degree 2) are presentedRavninski graf se imenuje alternirajoč, če imajo vsa sosednja vozlišča različne stopnje, prav tako pa tudi vsa sosednja lica. Alternirajoče ravninske grafe so prvič obravnavali leta 2008. Ta članek povzema dosedanje raziskave o alternirajočih ravninskih grafih. Obstajata dva najmanjša alternirajoča ravninska grafa, vsak od njiju ima po 17 vozlič in 17 lic. Ni nobenega alternirajočega ravninskega grafa na 18 vozliščih, obstajajo pa alternirajoči ravninski grafi za vse grafe na 19 ali več vozliščih. Iz majhne množice začetnih gradnikov lahko konstruiramo alternirajoče ravninske grafe za vse grafe večjih redov. Veliko majhnih alternirajočih ravninskih grafov so našli z izdatno pomočjo računalnikov. V članek so vključeni teoretični rezultati o alternirajočih ravninskih grafih, v katerih so vse stopnje vozlišč elementi množice ?$\{3,4,5\}$?. Predstavljenih je tudi več razredov "šibko alternirajočih ravninskih grafov" (z vozlišči stopnje 2)TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije