On graphs with the smallest eigenvalue at least -1- square root 2, part III

angleški

2019

letnik 17, številka 2

Hoffmanov graf   najmanjša lastna vrednost   povezavni graf

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

Obstajajo številni rezultati o grafih, katerih najmanjša lastna vrednost je vsaj ?$-2$?. Kot orodje za raziskavo grafov, katerih lastne vrednosti so vsaj ?$-1 - \sqrt{2}$?, sta R. Woo in A. Neumaier vpeljala Hoffmanove grafe in ?$\mathcal{H}$?-povezavne grafe. Dokazala sta, da je graf, ki ima dovolj veliko najmanjšo stopnjo in katerega najmanjša lastna vrednost je vsaj ?$-1 - \sqrt{2}$?, tanek ?$\{\mathfrak h_2, \mathfrak h_5, \mathfrak h_7, \mathfrak h_9\}$?-povezavni graf. Po tem je T. Taniguchi raziskoval tanke ?$\{\mathfrak h_2, \mathfrak h_5\}$?-povezavne grafe. Po analogiji v tem članku razkrivamo pogoje, pod katerimi je strogi ?$\{\mathfrak h_1, \mathfrak h_4, \mathfrak h_7\}$-krov tankega $\{\mathfrak h_7\}$?-povezavnega grafa en sam, in popolnoma določimo minimalne prepovedane grafe za tanke $?\{\mathfrak h_7\}$?-povezavne grafe.

29.05.2020