448 KB56 KB200820252022Gorzkowska, AleksandraHenning, Michael A.Pilśniak, MonikaTumidajewicz, Elżbietaštevilka:2letnik:22P2.04 (18 str.)DOI:10.26493/1855-3974.2522.eb3COBISSID_HOST:116313603ISSN:1855-3966URN:URN:NBN:SI:doc-1VA4YAXCenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneapaired dominationpaired domination stabilityparna dominacijastabilnost parne dominacijePaired domination stability in graphs|A set ?$S$? of vertices in a graph ?$G$? is a paired dominating set if every vertex of ?$G$? is adjacent to a vertex in ?$S$? and the subgraph induced by ?$S$? contains a perfect matching (not necessarily as an induced subgraph). The paired domination number, ?$\gamma_{\mathrm{pr}} (G)$?, of ?$G$? is the minimum cardinality of a paired dominating set of ?$G$?. A set of vertices whose removal from ?$G$? produces a graph without isolated vertices is called a non-isolating set. The minimum cardinality of a non-isolating set of vertices whose removal decreases the paired domination number is the ?$\gamma_{\mathrm{pr}}^-$?-stability of ?$G$?, denoted ?$\mathrm{st}_{\gamma_{\mathrm{pr}}}^- (G)$?. The paired domination stability of ?$G$? is the minimum cardinality of a non-isolating set of vertices in ?$G$? whose removal changes the paired domination number. We establish properties of paired domination stability in graphs. We prove that if ?$G$? is a connected graph with ?$\gamma_{\mathrm{pr}} (G) \geq 4$?, then ?$\mathrm{st}_{\gamma_{\mathrm{pr}}}^- (G) \leq 2\Delta (G)$? where ?$\Delta (G)$? is the maximum degree in ?$G$?, and we characterize the infinite family of trees that achieve equality in this upper boundMnož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 enakostTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije