On the null spaces of quartic circulant graphs

angleški

2025

letnik 1, številka 1, article p1.04

cirkulantni graf   kvartični graf   ničelni prostor   orešni graf   singularni graf   sosednostna matrika

Univerza na Primorskem
(Obvezni izvod spletne publikacije)

Orešni graf je netrivialen enostaven graf, katerega sosednostna matrika ima enodimenzionalni ničelni prostor, pri čemer noben od njegovih neničelnih vektorjev ne vsebuje ničelnih elementov. Za cirkulantne grafe je znano, da so orešni grafi natanko tedaj, ko je njihova ničelnost ena. Ta dejstvo je avtor nedavno uporabil za dokaz, da obstaja d-regularen cirkulantni orešni graf reda n natanko tedaj, ko 4|d,2|n, d >0, skupaj z n?d+ 4 če d?8 4, in n?d+ 6 če 8|d, ter (n, d)?= (16,8). V tem delu se ukvarjamo s kvartičnimi cirkulantnimi grafi in razkrivamo več rezultatov glede njihovih ničelnih prostorov. Najprej izpeljemo eksplicitno formulo za izračun ničelnosti kateregakoli kvartičnega cirkulantnega grafa. Nadalje podamo popolno karakterizacijo orešnih grafov med temi grafi. Nazadnje določimo vse take grafe, ki dosegajo minimalno ali maksimalno ničelnost glede na dano velikost. Prav tako podajamo ekstremalne ničelne prostore teh grafov.

24.08.2026