Paired domination stability in graphs

angleški

2022

letnik 22, številka 2

parna dominacija   stabilnost parne dominacije

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

Množica ?$S$? vozlišč grafa ?$G$? je parna dominacijska množica, če je vsako vozlišče grafa ?$G$? sosedno nekemu vozlišču iz množice ?$S$? in če podgraf, induciran z množico ?$S$?, vsebuje popolno prirejanje (ne nujno kot induciran podgraf). Parno dominacijsko število, ?$\gamma_{\mathrm{pr}} (G)$?, grafa ?$G$? je minimalna moč parne dominacijske množice grafa ?$G$?. Množica vozlišč, katerih odstranitev iz ?$G$? nam da graf brez izoliranih vozlišč, se imenuje neizolativna množica. Minimalna moč neizolativne množice vozlišč, katerih odstranitev zmanjša parno dominacijsko število, je ?$\gamma_{\mathrm{pr}}^-$?-stabilnost grafa ?$G$?, označena z ?$\mathrm{st}_{\gamma_{\mathrm{pr}}}^- (G)$?. Stabilnost parne dominacije grafa ?$G$? je minimalna moč neizolativne množice vozlišč iz ?$G$?, katerih odstranitev spremeni parno dominacijsko število. Določimo lastnosti stabilnosti parne dominacije v grafih. Dokažemo: če je ?$G$? povezan graf in je ?$\gamma_{\mathrm{pr}} (G) \geq 4$?, potem je ?$\mathrm{st}_{\gamma_{\mathrm{pr}}}^- (G) \leq 2\Delta (G)$?, kjer je ?$\Delta (G)$? maksimalna stopnja vozlišč v grafu ?$G$?; karakteriziramo tudi neskončno družino dreves, za katere v tej zgornji meji velja enakost.

22.11.2022