Quartic integral Cayley graphs

angleški

2015

letnik 8, številka 2

Cayleyev graf   celoštevilski graf   homomorfizem grafov   ločno-tranzitiven   prirejanje napetosti   spekter grafa   vozliščno tranzitiven dvodelen dvojni krov

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Navajamo popolna seznama povezanih križnih, t.j. 4-regularnih celoštevilskih Cayleyevih grafov in povezanih 4-regularnih celoštevilskih ločno-tranzitivnih grafov. Celoštevilski graf je graf s samimi celoštevilskimi lastnimi vrednostmi. Cayleyev graf ?$\text{Cay}(\Gamma, S)$? za dano grupo ?$\Gamma$? in povezavno množico ?$S \subset \Gamma$? je graf z množico vozlišč ?$\Gamma$?, v katerem je vozlišče ?$a$? povezano z vozliščem ?$b$? če in samo če je ?$ba^{-1} \in S$?. Do izomorfizma natanko smo ugotovili, da je 32 povezanih 4-regularnih celoštevilskih Cayleyevih grafov; 17 od njih je dvodelnih. Mnoge od njih se da realizirati na mnogo različnih načinov z uporabo ne-izomorfnih izbir za ?$\Gamma$? in/ali ?$S$?. Graf se imenuje ločno-tranzitiven, če njegova grupa avtomorfizmov deluje tranzitivno na urejenih parih sosednjih vozlišč. Do izomorfizma natanko obstaja 27 4-regularnih celoštevilskih ločno tranzitivnih grafov. Med temi 27 grafi je 16 dvodelnih in 16 Cayleyevih. Tudi številni drugi 4-regularni celoštevilski grafi so kvocienti naših Cayleyevih ali ločno-tranzitivnih grafov. V splošnem smo našli 9 novih spektrov, ki jih lahko realiziramo z dvodelnimi 4-regularnimi celoštevilskimi grafi.

29.05.2020