Paired domination stability in graphs - Gorzkowska, Aleksandra (Ars mathematica contemporanea, 2022)
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, ?$γ_{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 ?$γ_{pr}^-$?-stabilnost grafa ?$G$?, označena z ?$st_{γ_{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 ?$γ_{pr} (G) ≥ 4$?, potem je ?$st_{γ_{pr}}^- (G) ≤ 2Δ (G)$?, kjer je ?$Δ (G)$? maksimalna stopnja vozlišč v grafu ?$G$?; karakteriziramo tudi neskončno družino dreves, za katere v tej zgornji meji velja enakost.
Keywords: paired domination; paired domination stability; parna dominacija; stabilnost parne dominacije