On the inertia of weighted (k - 1)-cyclic graphs

angleški

2016

letnik 11, številka 2

sosednostna matrika   utežen k-cikličen graf   vztrajnost

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

Naj bo ?$G_w$? utežen graf. Vztrajnost grafa ?$G_w$? je urejena trojica ?$\mathrm{In} (G_w) = (i_+ (G_w), i_ - (G_w), i_0(G_w))$?, kjer so ?$i _+ (G_w)$?, ?$i_- (G_w)$?, ?$i_0(G_w)$? število pozitivnih, negativnih in ničelnih lastnih vrednosti sosednostne matrike ?$A(G_w)$? grafa ?$G_w$? upoštevaje njihove večkratnosti. Enostaven ?$n$?-vozliščni povezan graf se imenuje ?$(k -1)$?-cikličen graf, če je število njegovih povezav enako ?$n+k-2$?. Naj bo ?$\theta(r_1, r_2, \dots, r_k)_w$? ?$n$?-vozliščni enostaven utežen graf, ki ga dobimo iz ?$k$? uteženih poti ?$(P_{r_1})_w, ((P_{r_2})_w, \dots,(P_{r_k})_w$? z identificiranjem njihovih začetnih vozlišč ter njihovih končnih vozlišč. Vpeljimo ?$\Theta_ k: = \{\theta(r_1, r_2, \dots, r_k)_w \colon r_1 + r_2 + \dots + r_k = n + 2k - 2\}$?. Študiramo vztrajnost uteženega grafa ?$\theta(r_1, r_2, \dots, r_k)_w$?. Prav tako študiramo utežene ?$(k - 1)$?-ciklične grafe, ki vsebujejo ?$\theta(r_1, r_2, \dots, r_k)_w$? kot induciran podgraf. Karakteriziramo tiste grafe izmed ?$\Theta_ k$?, ki imajo ekstremno vztrajnost. Naši rezultati posplošujejo tiste, ki sta jih dobila Tan in Liu leta 2013 ter Yu in dr. leta 2014.

29.05.2020