20.500.12556/DiRROS-18405 Computational complexity aspects of super domination Let ▫$G$▫ be a graph. A dominating set ▫$D\subseteq V(G)$▫ is a super dominating set if for every vertex ▫$x\in V(G) \setminus D$▫ there exists ▫$y\in D$▫ such that ▫$N_G(y)\cap (V(G)\setminus D)) = \{x\}$▫. The cardinality of a smallest super dominating set of ▫$G$▫ is the super domination number of ▫$G$▫. An exact formula for the super domination number of a tree ▫$T$▫ is obtained, and it is demonstrated that a smallest super dominating set of ▫$T$▫ can be computed in linear time. It is proved that it is NP-complete to decide whether the super domination number of a graph ▫$G$▫ is at most a given integer if ▫$G$▫ is a bipartite graph of girth at least ▫$8$▫. The super domination number is determined for all ▫$k$▫-subdivisions of graphs. Interestingly, in half of the cases the exact value can be efficiently computed from the obtained formulas, while in the other cases the computation is hard. While obtaining these formulas, II-matching numbers are introduced and proved that they are computationally hard to determine. super domination number trees bipartite graphs k-subdivision of a graph computational complexity matching II-matching number število super dominacije drevesa dvodelni grafi k-subdivizija grafa računska zahtevnost prirejanje število II-prirejanja true false false Angleški jezik Slovenski jezik Neznano 2024-03-14 14:08:32 2024-03-14 14:08:32 2024-03-15 03:36:24 0000-00-00 00:00:00 2023 0 0 14 str. art. no. 114137 Vol. 975 Oct. 2023 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2023-10-01 519.17 0304-3975 10.1016/j.tcs.2023.114137 162318851 https://www.sciencedirect.com/science/article/pii/S0304397523004504 1 f62b4340-e203-11ee-9dd4-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25062 1-s2.0-S0304397523004504-main.pdf 1-s2.0-S0304397523004504-main.pdf 1 E30A15BCE1A2914775BF45D96D19B10F 7c65152373627b0dc6047f698b4050163075bf1ad1d775eb7729bb03ce21fd2d 14fa3961-e204-11ee-9dd4-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25063 Inštitut za matematiko, fiziko in mehaniko 0 0 0