20.500.12556/RUL-153123 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 II-matchings število super dominacije drevesa dvodelni grafi k-subdivizija grafa računska zahtevnost prirejanje število II-prirejanja true false true Angleški jezik Slovenski jezik Članek v reviji 2023-12-18 15:31:48 2023-12-18 15:31:51 2023-12-19 03:44:22 0000-00-00 00:00:00 2023 0 0 14 str. art. 114137 Vol. 975 Oct. 2023 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 0304-3975 10.1016/j.tcs.2023.114137 162318851 1-s2.0-S0304397523004504-main.pdf 1-s2.0-S0304397523004504-main.pdf 1 F964F67C1CBEFCAB90B9245C145742B4 5fd1fcd55127ce26a88e9f2aa4810598ae296ba3ee99360e711cbfbba88c69c9 90f9cc96-9db2-11ee-a59a-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=179018 https://www.sciencedirect.com/science/article/pii/S0304397523004504 1 2efde8f1-9db2-11ee-a59a-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=179017 Fakulteta za matematiko in fiziko 0 0 0