Quartic integral Cayley graphs - Minchenko, Marsha (Ars mathematica contemporanea, 2015)
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}(Γ, S)$? za dano grupo ?$Γ$? in povezavno množico ?$S \subset Γ$? je graf z množico vozlišč ?$Γ$?, 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 ?$Γ$? 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.
Keywords: arc-transitive; Cayley graph; Cayleyev graf; celoštevilski graf; graph homomorphism; graph spectrum; homomorfizem grafov; integral graph; ločno-tranzitiven; prirejanje napetosti; spekter grafa; vertex-transitive bipartite double cover; voltage assignment; vozliščno tranzitiven dvodelen dvojni krov