# Computational complexity aspects of super domination

Csilla Bujtás1,4 Nima Ghanbari2 Sandi Klavžar1,3,4

###### Abstract

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 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.

1 Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
2 Department of Informatics, University of Bergen,

P.O. Box 7803, 5020 Bergen, Norway

<EMAIL_ADDRESS>
3 Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

4 Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

Keywords: super domination number; tree; bipartite graph; $k$-subdivision of a
graph; computational complexity; matching; II-matching number

AMS Subj. Class.: 05C69, 68Q25

##  1 Introduction

Let $G=(V(G),E(G))$ be a graph. Then $D\subseteq V(G)$ is a dominating set if
every vertex in $\overline{D}=V(G)\setminus D$ is adjacent to at least one
vertex in $D$. The domination number $\gamma(G)$ of $G$ is the minimum
cardinality of a dominating set of $G$. Graph domination theory has been
extensively researched so far. To capture the current state of the field, we
refer the reader to two recent edited books [8, 9].

Many variations of the domination have been introduced, some of which are
significant and important (such as total domination and connected domination),
while others are of only sporadic importance. In our view, the group of
significant domination concepts includes super domination which was introduced
in 2015 by Lemańska, Swaminathan, Venkatakrishnan, and Zuazua [16].

It is a classically known fact, that a dominating set $D$ of $G$ is minimal if
and only if every vertex from $D$ has a private neighbor in
$\overline{D}=V(G)\setminus D$. As a dual concept one says that a dominating
set $D$ of $G$ is a super dominating set of $G$, if for every vertex
$x\in\overline{D}$ there exists $y\in D$ such that
$N_{G}(y)\cap\overline{D}=\\{x\\}$. (As usual, $N_{G}(v)$ stands for the open
neighborhood of $v$ in $G$ and $N_{G}[v]$ for the closed neighborhood of $v$
in $G$.) The cardinality of a smallest super dominating set of $G$ is the
super domination number $\gamma_{\rm sp}(G)$ of $G$. A super dominating set of
cardinality $\gamma_{\rm sp}(G)$ is briefly called a $\gamma_{\rm sp}$-set.
The initial study of the concept has been followed by several sequels, of
which the reader is referred to [5, 12, 14, 20, 26].

The subdivision of a graph $G$ is the graph obtained from $G$ by replacing
each edge with a disjoint path of length $2$ and is denoted by $S(G)$. More
generally, if $k\geq 1$, then the graph $S_{k}(G)$ is obtained from $G$ by
replacing each edge with a disjoint path of length $k+1$, that is, subdividing
each of its edges $k$ times. Clearly, $S(G)=S_{1}(G)$. Some authors use the
term complete $k$-subdivision for what we call $k$-subdivision, but since all
our subdivisions are complete, we simplify the terminology. The concept of
$k$-subdivisions is ubiquitous in graph theory, here we cite its presence in
graph colorings [1, 22], spectral graph theory [3], structural graph theory
[17, 25], and chemical graph theory [2, 11].

In this article we discuss various aspects of super domination, which are in
one way or another intertwined with the computational complexity of the
problem of determining the super domination number. In the next section we
recall some definitions and known results, and state a useful characterization
of super dominating sets. Super domination has already been considered on
trees from several perspectives, see [14, 16, 20, 26]. By now, only sharp
upper and lower bounds have been obtained. In Section 3 we fill this gap by
providing an exact formula for the super domination number of a tree.
Moreover, we demonstrate that if $T$ is a tree, then $\gamma_{\rm sp}(T)$ as
well as a $\gamma_{\rm sp}$-set of $T$ can be computed in linear time. On the
negative side, in Section 4, we prove that it is NP-complete to decide whether
$\gamma_{\rm sp}(G)\leq k$ holds if $G$ is a bipartite graph of girth
$g(G)\geq 8$ and the positive integer $k$ is part of the input. In our longest
part of the paper, Section 5, we consider $k$-subdivisions of arbitrary
graphs. Depending on $k\bmod 4$, four closed formulas for $\gamma_{\rm
sp}(S_{k}(G))$ are proved. When $k\bmod 4\in\\{1,3\\}$, the corresponding
formulas depend only of $k$, the size of $G$, and a simple condition on the
cycles of $G$. Note that in these two cases $S_{k}(G)$ is bipartite. On the
other hand, if $k\bmod 4=0$, then $\gamma_{\rm sp}(S_{k}(G))$ is a function of
$\gamma_{\rm sp}(G)$ also, and if $k\bmod 4=2$, then $\gamma_{\rm
sp}(S_{k}(G))$ depends also on the cardinality of a largest matching that
admits a partition into two induced matchings. We name such matchings as II-
matchings and prove that it is NP-hard to compute the maximum size of such
matchings. It follows that for each even $k$, it is also NP-hard to determine
$\gamma_{\rm sp}(S_{k}(G))$.

##  2 Preliminaries

The order and the size of a graph $G$ will be denoted by $n(G)$ and $m(G)$,
respectively. If $D$ is a super dominating set of $G$ and if for a vertex
$x\in\overline{D}$ the vertex $y\in D$ has the property
$N_{G}(y)\cap\overline{D}=\\{x\\}$, then we will say that $x$ is super
dominated by $y$.

Let $G$ be a graph. Then the independence number of $G$ will be denoted by
$\alpha(G)$, the matching number of $G$ by $\alpha^{\prime}(G)$, and the
vertex cover number of $G$ by $\beta(G)$. A set $X\subseteq V(G)$ is a
$2$-packing of $G$ if $d_{G}(u,v)\geq 3$ holds for each pair of vertices
$u,v\in X$. In other words, each pair of vertices of $X$ has disjoint closed
neighborhoods. The cardinality of a smallest $2$-packing of $G$ will be
denoted by $\rho(G)$.

The path in $S_{k}(G)$ obtained by $k$ times subdividing an edge $uv\in E(G)$
will be denoted by $P_{uv}$ and addressed to as a super edge. The vertices of
$P_{uv}$ will be denoted by $u,(uv)_{1},\ldots,(uv)_{k},v$. Note that
$n(S_{k}(G))=n(G)+k\cdot m(G)$ and $m(S_{k}(G))=(k+1)m(G)$. We say that a
graph is a $k$-subdivision graph if it can be obtained as a $k$-subdivision of
some graph.

We next recall a few results on the super domination number needed later on.

###### Theorem 2.1

[16] If $G$ is a graph without isolated vertices, then,

$1\leq\gamma(G)\leq\frac{n}{2}\leq\gamma_{\rm sp}(G)\leq n(G)-1\,.$

###### Theorem 2.2

[12, Theorem 3, Corollary 2] If $G$ is a graph with $n(G)\geq 2$, then

$n(G)-\alpha^{\prime}(G)\leq\gamma_{\rm sp}(G)\leq n(G)-\rho(G).$

Since $n(G)=\alpha(G)+\beta(G)$ in general and $\alpha^{\prime}(G)=\beta(G)$
when $G$ is bipartite, Theorem 2.2 implies that if $G$ is bipartite, then
$\gamma_{\rm sp}(G)\geq\alpha(G)$.

###### Theorem 2.3

[16] The following exact values are valid.

  * (i)

If $n\geq 2$, then $\gamma_{\rm sp}(P_{n})=\lceil\frac{n}{2}\rceil$.

  * (ii)

If $n\geq 3$, then

$\gamma_{\rm
sp}(C_{n})=\left\\{\begin{array}[]{ll}\lceil\frac{n+1}{2}\rceil;&n\equiv
2\bmod 4,\\\ \\\ \lceil\frac{n}{2}\rceil;&\mbox{otherwise}.\end{array}\right.$

  * (iii)

If $n\geq 2$, then $\gamma_{\rm sp}(K_{1,n})=n$.

Let $G$ be a graph, and let $D$ be a super dominating set of $G$. For each
$u\in\overline{D}$, select an arbitrary vertex $u^{\prime}\in D$ such that $u$
is the unique neighbor of $u^{\prime}$ in $\overline{D}$, that is,
$N(u^{\prime})\cap\overline{D}=\\{u\\}$. Then we say that the set

$D^{\ast}=\\{u^{\prime}\in D:\ u\in\overline{D}\\}$

is a core of $D$. By this definition, there exists a matching between
$\overline{D}$ and $D^{\ast}$ that covers $\overline{D}\cup D^{\ast}$.
Moreover, the following result holds which seems of independent interest.
Before stating it, we introduce a notation. For two disjoint vertex sets
$A,B\subseteq V(G)$ let $E_{G}[A,B]$ denote the set of all edges between $A$
and $B$ in $G$.

###### Lemma 2.4

Let $A$ and $B$ be two disjoint vertex sets of a graph $G$. Then
$D=\overline{A}$ is a super dominating set and $B$ is a core of $D$ if and
only if $E_{G}[A,B]$ is a matching that covers all vertices in $A\cup B$.

Proof. Suppose that $D=\overline{A}$ is a super dominating set and let $B$ be
its core. By definition of the core, every vertex from $B$ has exactly one
neighbor from $A$, so that $|N_{G}(x)\cap B|=1$ if $x\in A$ and $|N_{G}(y)\cap
A|=1$ whenever $y\in B$. It shows that $E_{G}[A,B]$ is a matching that covers
$A\cup B$.

Now, suppose that $A$, $B$ are disjoint vertex sets in $G$ such that
$E_{G}[A,B]$ is a matching that covers $A\cup B$. Define $D=\overline{A}$ and
observe that every $x\in A$ is super dominated by the vertex $y$ that is the
pair of $x$ in the matching $E_{G}[A,B]$. Indeed, by our assumption, $y\in D$
and $N_{G}(y)\cap A=\\{x\\}$. It also follows that $B$ can be considered as a
core of $D$. $\square$

Note that Lemma 2.4 implies the lower bound of Theorem 2.2. Moreover, it also
implies the following.

###### Corollary 2.5

If $D$ is a super dominating set of a graph $G$, and $D^{\ast}$ is a core of
$D$, then $(D\setminus D^{\ast})\cup\overline{D}$ is also a super dominating
set of $G$. In particular, if $D$ is a $\gamma_{\rm sp}$-set, then
$(D\setminus D^{\ast})\cup\overline{D}$ is also a $\gamma_{\rm sp}$-set.

Proof. The first assertion follows directly by Lemma 2.4. And as $|(D\setminus
D^{\ast})\cup\overline{D}|=|D|$, the second assertion also follows. $\square$

###### Corollary 2.6

If $G$ is a graph and $v\in V(G)$, then there exists a $\gamma_{\rm sp}$-set
of $G$ that contains $v$.

Proof. Let $D$ be an arbitrary $\gamma_{\rm sp}$-set of $G$. If $v\in D$ there
is nothing to prove. Otherwise consider a core $D^{\ast}$ of $G$. Then
$v\in(D\setminus D^{\ast})\cup\overline{D}$ which is a $\gamma_{\rm sp}$-set
by Corollary 2.5. $\square$

It is interesting to compare Corollary 2.6 with [26, Proposition 2.4] which
asserts that if $v$ is a leaf of a non-trivial tree $T$, then there exists a
$\gamma_{\rm sp}$-set of $T$ which does not contain $v$.

##  3 Super domination number of trees

The main result of this section reads as follows.

###### Theorem 3.1

If $T$ is a tree, then $\gamma_{\rm sp}(T)=n(T)-\alpha^{\prime}(T)$. Moreover,
a $\gamma_{\rm sp}$-set of $T$ can be determined in linear time over the class
of trees.

Proof. Consider a maximum matching $M$ in $T$. We will show that $V(M)$ can be
partitioned into two vertex sets $A$ and $B$ such that $E_{T}[A,B]=M$. By
Lemma 2.4, it will imply that there is a super dominating set of cardinality
$n(T)-|A|=n(T)-|M|=n(T)-\alpha^{\prime}(T)$. Together with the inequality
$\gamma_{\rm sp}(G)\geq n(G)-\alpha^{\prime}(G)$ from Theorem 2.1 we obtain
$\gamma_{\rm sp}(T)=n(T)-\alpha^{\prime}(T)$ for the tree, as stated.

To construct the sets $A$ and $B$, we first specify a root vertex $r$ such
that $r$ is covered by $M$. We first put $r$ into $A$ and consider the
children $v_{1},\dots,v_{k}$ of $r$. If $rv_{i}\in M$, we put $v_{i}$ into
$B$; if $rv_{i}\notin M$ but $v_{i}\in V(M)$, we put $v_{i}$ into $A$; if
$v_{i}\notin V(M)$, then $v_{i}$ remains outside $A\cup B$. We continue
analogously while traversing the tree in preorder. When we decide about the
children $u_{1},\dots,u_{\ell}$ of a vertex $u$, we have three main cases.

  * •

First, let $u\notin V(M)$. Then, if $u_{i}\in V(M)$, we put $u_{i}$ into $A$;
if $u_{i}\notin V(M)$, we put it into neither $A$ nor $B$.

  * •

Suppose that $u\in A$. If $uu_{i}\in M$, put $u_{i}$ into $B$; if
$uu_{i}\notin M$ and $u_{i}\in V(M)$, put $u_{i}$ into $A$; if $u_{i}\notin
V(M)$, leave $u_{i}$ outside $A\cup B$.

  * •

The case when $u\in B$ is analogous to the previous one. If $uu_{i}\in M$, we
put $u_{i}$ into $A$; if $uu_{i}\notin M$ and $u_{i}\in V(M)$, we put $u_{i}$
into $B$; if $u_{i}\notin V(M)$, we leave $u_{i}$ outside $A\cup B$.

It is clear that for the constructed sets, $(A,B)$ results in a partition of
$V(M)$ such that $M=E_{T}[A,B]$. Therefore, by Lemma 2.4, $D=\overline{A}$ is
a super dominating set in $T$ and we may infer $\gamma_{\rm
sp}(T)=n(T)-\alpha^{\prime}(T)$.

Concerning the construction of a $\gamma_{\rm sp}$-set of a tree, we remark
that a maximum matching of a tree can be obtained in linear time. Once the
matching $M$ is in hand, the algorithm described in the proof assigns labels
$A$, $B$, $\overline{A\cup B}$ to the vertices in preorder, visiting every
vertex only once and making a choice according to local properties. Thus, the
determination of a $\gamma_{\rm sp}$-set of a tree can be done in linear time
as stated. $\square$

Extending the definition of the subdivision of a graph by setting
$S_{0}(G)=G$, the following result can be considered as a generalization of
Theorem 2.3(iii).

###### Corollary 3.2

If $k\geq 0$ and $n\geq 2$, then

$\gamma_{\rm
sp}(S_{k}(K_{1,n}))=\left\\{\begin{array}[]{ll}\frac{n(k+2)}{2};&k\
\mbox{even},\\\ \\\ \frac{n(k+1)}{2}+1;&k\ \mbox{odd}.\end{array}\right.$

Proof. By Theorem 2.3(iii), $\gamma_{\rm sp}(S_{0}(K_{1,n}))=\gamma_{\rm
sp}(K_{1,n})=n$, hence the assertion holds for $k=0$.

It is straightforward to see that if $k\geq 2$ is even, then
$\alpha^{\prime}(S_{k}(K_{1,n}))=n\frac{k}{2}+1$, and if $k\geq 1$ is odd,
then $\alpha^{\prime}(S_{k}(K_{1,n}))=n\frac{k+1}{2}$. The result now follows
by applying Theorem 3.1. $\square$

##  4 Bipartite graphs

By Theorem 3.1, the super domination number and a $\gamma_{\rm sp}$-set can be
determined in linear time for trees. In this section we show that the same
problem is NP-hard over the class of bipartite graphs.

###### Theorem 4.1

  * $(a)$

It is NP-complete to decide whether $\gamma_{\rm sp}(G)\leq k$ holds if $G$ is
a bipartite graph of girth $g(G)\geq 8$ and the positive integer $k$ is part
of the input.

  * $(b)$

It is NP-complete to decide whether $\gamma_{\rm
sp}(G)=n(G)-\alpha^{\prime}(G)$ holds if $G$ is bipartite and $g(G)\geq 8$.

Proof. As $\gamma_{\rm sp}(G)\geq n(G)-\alpha^{\prime}(G)$ holds for every
graph $G$, the equality in $(b)$ is equivalent to the inequality $\gamma_{\rm
sp}(G)\leq n(G)-\alpha^{\prime}(G)$. Thus, both decision problems $(a)$ and
$(b)$ belong to NP. In order to prove that the decision problems in $(a)$ and
$(b)$ are NP-hard, we present a polynomial-time reduction from 3-SAT problem,
which is a classical NP-complete problem [6].

Let $F$ be a $3$-SAT instance with clauses $C_{1},\dots,C_{\ell}$ over the
Boolean variables $x_{1},\dots,x_{s}$. We construct a graph $G_{F}$ such that
$F$ is satisfiable if and only if $\gamma_{\rm sp}(G_{F})\leq 4s+3\ell+1$.

#### Construction of $G_{F}$.

For each variable $x_{i}$, we take eight vertices that form the set
$X_{i}=\\{x_{i}^{-},x_{i}^{+},x_{i}^{1},\dots,x_{i}^{6}\\}$ and add edges such
that $x_{i}^{1}x_{i}^{-}x_{i}^{2}x_{i}^{4}x_{i}^{5}x_{i}^{+}x_{i}^{6}$ is an
induced path and $x_{i}^{3}x_{i}^{4}$ is a pendant edge in $G_{F}$. Each
clause $C_{j}$, will be represented by a vertex $c_{j}$ in $G_{F}$. If $x_{i}$
is a literal in $C_{j}$, we add an edge $x_{i}^{+}c_{j}$ and subdivide it by a
vertex $y_{j,i}$. Similarly, if $\neg x_{i}$ is a literal in $C_{j}$, we add
an edge $x_{i}^{-}c_{j}$ and subdivide it by a vertex $y_{j,i}$. The set of
these subdivision vertices will be denoted by $Y$. To finish the construction,
we add two further vertices, namely $v$ and $v^{*}$, and the edges $vv^{*}$
and $v^{*}c_{j}$ for each $j\in[\ell]$. (See Fig. 1 for illustration.) It is
easy to check that the constructed graph $G_{F}$ is bipartite with
$n(G_{F})=8s+4\ell+2$ and, moreover, if $G$ is not a tree111We may suppose,
without loss of generality, that $G_{F}$ is of girth of at least $8$. Indeed,
if $G_{F}$ is a tree, we may consider the formula
$F^{\prime}=F\wedge(x_{1}\vee\neg x_{1}\wedge x_{2})$. Clearly, a truth
assignment satisfies $F$ if and only if it satisfies $F^{\prime}$, and
$\gamma_{\rm sp}(G_{F})=n(G_{F})-\alpha^{\prime}(G_{F})$ if and only if the
same is true for $G_{F^{\prime}}$., then its girth is at least $8$.

0.6 0.6
$v$$v^{\star}$$c_{1}$$c_{2}$$c_{3}$$x_{1}^{1}$$x_{1}^{2}$$x_{1}^{3}$$x_{1}^{4}$$x_{1}^{5}$$x_{1}^{6}$$x_{1}^{+}$$x_{1}^{-}$$x_{2}^{+}$$x_{3}^{+}$$x_{4}^{+}$$x_{2}^{-}$$x_{3}^{-}$$x_{4}^{-}$

Figure 1: Graph $G_{F}$ for the formula $F=(\neg x_{1}\vee x_{2}\vee\neg
x_{3})\wedge(x_{1}\vee x_{3}\vee\neg x_{4})\wedge(\neg x_{2}\vee x_{3}\vee
x_{4})$ constructed in the proof of Theorem 4.1

We first prove that $\alpha^{\prime}(G_{F})=4s+\ell+1$. Let $M$ be a matching
in $G_{F}$. For every $i\in[s]$, the vertices in $X_{i}$ may be incident with
at most four edges from $M$. Each clause vertex $c_{j}$ may be incident with
one edge from $M$. The only edge in $G_{F}$ that is not covered by the
previous vertices is $vv^{*}$ and it may belong to $M$ only if
$c_{j}v^{*}\notin M$ holds for all $j\in[\ell]$. This proves
$\alpha^{\prime}(G_{F})\leq 4s+\ell+1$ and it is easy to find a matching of
size $4s+\ell+1$ in $G_{F}$. Therefore, $\alpha^{\prime}(G_{F})=4s+\ell+1$.
Moreover, every maximum matching contains the following edges: $vv^{*}$;
$x_{i}^{2}x_{i}^{3}$ and $x_{i}^{4}x_{i}^{5}$ for every $i\in[s]$; one edge
between $c_{j}$ and $Y$ for every $j\in[\ell]$; one edge between $x_{i}^{+}$
and $Y\cup\\{x_{i}^{6}\\}$ and one edge between $x_{i}^{-}$ and
$Y\cup\\{x_{i}^{1}\\}$ for every $i\in[s]$.

Now, suppose that $\gamma_{\rm sp}(G_{F})\leq 4s+3\ell+1$ holds and prove that
the $3$-SAT formula $F$ is satisfiable. Since
$\alpha^{\prime}(G_{F})=4s+\ell+1$, by Theorem 2.1 the condition is equivalent
with $\gamma_{\rm sp}(G_{F})=4s+3\ell+1$. Let $D$ be a minimum $\gamma_{\rm
sp}$-set in $G_{F}$. By Lemma 2.4, there are two disjoint vertex sets
$A=\overline{D}$ and $B=D^{\ast}$ such that $|A|=|B|=n(G_{F})-\gamma_{\rm
sp}(G_{F})=4s+\ell+1$ and $E_{G_{F}}[A,B]$ is a matching $M$. Since $M$ is a
maximum matching, for every $i\in[s]$, we have $x_{i}^{-},x_{i}^{+}\in V(M)$
and $x_{i}^{2}x_{i}^{3},x_{i}^{4}x_{i}^{5}\in M$. By the condition
$E_{G_{F}}[A,B]=M$, if $x_{i}^{+}\in A$ holds, then $x_{i}^{5}\in A$ and
$x_{i}^{4},x_{i}^{2},x_{i}^{-}\in B$ follow. Analogously, if $x_{i}^{+}\in B$,
we may conclude $x_{i}^{-}\in A$. Therefore, we may define a truth function
$\varphi\colon X\to\\{\mbox{true, false}\\}$ in the following way:

$\varphi(x_{i})=\left\\{\begin{array}[]{ll}\mbox{true};&x_{i}^{+}\in B,\\\ \\\
\mbox{false};&x_{i}^{-}\in B.\end{array}\right.$

By Corollary 2.5, we may suppose that $v^{*}\in A$. Consider a clause vertex
$c_{j}$. As $v^{*}c_{j}\notin M$ and $c_{j}\in V(M)$, the vertex $c_{j}$ also
belongs to $A$. If $y_{j,i}$ is the vertex from $Y$ such that $c_{j}y_{j,i}\in
M$, then $y_{j,i}\in B$. Suppose first that the other neighbor of $y_{j,i}$ is
$x_{i}^{+}$ i.e., the clause $C_{j}$ contains the positive literal $x_{i}$. As
$x_{i}\in V(M)$ and $y_{j,i}$ is already covered by one matching edge,
$y_{j,i}x_{i}^{+}\notin M$ and $x_{i}^{+}\in B$ holds. Then, by definition, we
have $\varphi(x_{i})=\mbox{true}$ and the positive literal $x_{i}^{+}$
satisfies clause $C_{j}$. Similarly, if the other neighbor of $y_{j,i}$ is
$x_{i}^{-}$, then $C_{j}$ contains the literal $\neg x_{i}$. As
$E_{G_{F}}[A,B]=M$, we may infer $x_{i}^{-}\in B$. It implies
$\varphi(x_{i})=\mbox{false}$ and hence, the literal $\neg x_{i}$ satisfies
$C_{j}$. It is true for all clauses in $F$ and proves the satisfiability of
the formula.

To prove the other direction of the statement, we suppose that $F$ is
satisfied by a truth assignment $\phi\colon X\to\\{\mbox{true, false}\\}$. Let
us define

$D=Y\cup\\{v\\}\cup\\{x_{i}^{1},x_{i}^{3},x_{i}^{5},x_{i}^{+}\colon
i\in[s]\mbox{ and }\phi(x_{i})=\mbox{true}\\}$
$\cup\,\\{x_{i}^{-},x_{i}^{2},x_{i}^{4},x_{i}^{6}\colon i\in[s]\mbox{ and
}\phi(x_{i})=\mbox{false}\\}.$

It is easy to check that $D$ is a super dominating set and $|D|=4s+3\ell+1$.
Indeed, it is enough to consider the following connections:

  * •

$v$ super dominates $v^{*}$;

  * •

if $\phi(x_{i})=\mbox{true}$, then $x_{i}^{1}$ super dominates $x_{i}^{-}$,
$x_{i}^{3}$ super dominates $x_{i}^{2}$, $x_{i}^{5}$ super dominates
$x_{i}^{4}$, and $x_{i}^{+}$ super dominates $x_{i}^{6}$;

  * •

if $\phi(x_{i})=\mbox{false}$, then $x_{i}^{-}$ super dominates $x_{i}^{1}$,
$x_{i}^{2}$ super dominates $x_{i}^{3}$, $x_{i}^{4}$ super dominates
$x_{i}^{5}$, and $x_{i}^{6}$ super dominates $x_{i}^{+}$;

  * •

if a clause $C_{j}$ is satisfied by a literal $x_{i}$ or $\neg x_{i}$, then
the corresponding subdivision vertex $y_{j,i}\in D$ and
$N(y_{j,i})\cap\overline{D}=\\{c_{j}\\}$ and thus, $y_{j,i}$ super dominates
$c_{j}$.

We have proved that the NP-complete problem 3-SAT can be reduced to the
problem of deciding whether $\gamma_{\rm sp}(G_{F})\leq
n(G_{F})-\alpha^{\prime}(G_{F})=4s+3\ell+1$ holds. The reduction can be done
in polynomial time and therefore, we may conclude that both problems $(a)$ and
$(b)$ are NP-complete. $\square$

##  5 Super domination in subdivision graphs

###  5.1 $(4t+3)$-subdivisions

For a graph $G$, let $\widehat{n}(G)$ be the maximum size of a subset
$\widehat{V}\subseteq V(G)$ such that there exists an injective mapping
$\phi:\widehat{V}\to E(G)$ so that $v\in\phi(v)$ holds for every
$v\in\widehat{V}$. We will say that a function $\phi$ with these properties is
a _DR-function_ in $G$; and if $\widehat{n}(G)=n(G)$, we may say that the
vertex set of $G$ has a _set of distinct representatives (SDR)_.

###### Lemma 5.1

If $G$ is a connected graph that is not a tree, then $\widehat{n}(G)=n(G)$. If
$G$ is a tree, then $\widehat{n}(G)=n(G)-1$.

Proof. Associate every vertex $v\in V(G)$ with the set $E(v)$ of edges that
are incident to $v$. First, consider a proper subset $X$ of $V(G)$ and the set
$E(X)=\bigcup_{v\in X}E(v)$. In the induced subgraph $G[X]$, every component
$F$ satisfies $m(F)\geq n(F)-1$ and, since $G$ is connected and $F\neq G$, the
vertex set of $F$ is incident with at least one edge not contained in the
subgraph $F$. These extra edges are pairwise different for different
components of $G[X]$. We therefore conclude $|E(X)|\geq|X|$ for every vertex
set $X\subsetneqq V(G)$. Notice that it is true for every graph $G$, no matter
$G$ is a tree or not. Consider now the case $X=V(G)$. If $G$ is not a tree,
then $n(G)=|X|\leq|E(X)|=m(G)$ and, as Hall’s Condition is satisfied for each
$X\subseteq V(G)$, there exists a system of distinct representatives for the
vertex set of $G$. That is, $\widehat{n}(G)=n(G)$. If $G$ is a tree,
$|V(G)|>|E(G)|$ and there is no SDR for the vertex set. On the other hand, if
we consider $G$ as a tree rooted in $r$ and map every non-root vertex $v$ to
the edge between $v$ and its parent, the obtained mapping is a DR-function
from $V(G)\setminus\\{r\\}$ to $E(G)$. It proves $\widehat{n}(G)=n(G)-1$ for
every tree $G$. $\square$

###### Theorem 5.2

For every connected graph $G$ and integer $k\equiv 3\bmod 4$,

$\gamma_{\rm
sp}(S_{k}(G))=\left\\{\begin{array}[]{ll}\frac{k+1}{2}\,m(G)+1;&\mbox{$G$ is a
tree},\\\ \\\ \frac{k+1}{2}\,m(G);&\mbox{otherwise}.\end{array}\right.$

Proof. Let $V(G)=\\{v_{1},\ldots,v_{n}\\}$ and $k=4t+3$. Observe that
$n(S_{k}(G))=n+k\,m(G)$. We first show that

$\displaystyle\alpha^{\prime}(S_{k}(G))\leq\frac{k-1}{2}\,m(G)+\widehat{n}(G).$
(1)

Let $M$ be a maximum matching in $S_{k}(G)$. For every super edge
$P_{v_{i}v_{j}}$, we have two possibilities:

  * $(a)$

$M$ contains at most $\frac{k-1}{2}$ edges from $P_{v_{i}v_{j}}$;

  * $(b)$

$M$ contains exactly $\frac{k+1}{2}$ edges from $P_{v_{i}v_{j}}$ and at least
one of $v_{i}$ and $v_{j}$ is covered by a matching edge belonging to
$P_{v_{i}v_{j}}$.

As each $v_{i}\in V(G)$ is covered by at most one edge from $M$, the number of
super edges satisfying $(b)$ is at most $n$. Moreover, if $(b)$ is valid for a
super edge $P_{v_{i}v_{j}}$, then $v_{i}(v_{i}v_{j})_{1}\in M$ or
$(v_{i}v_{j})_{k}v_{j}\in M$. In the first case, we define
$\phi(v_{i})=v_{i}v_{j}$, while we set $\phi(v_{j})=v_{i}v_{j}$ in the latter
case. (If both edges $v_{i}(v_{i}v_{j})_{1}$ and $(v_{i}v_{j})_{k}v_{j}$
belong to $M$, then to keep $\phi$ injective, we set just
$\phi(v_{i})=v_{i}v_{j}$ for the smaller index $i$.) As $\phi$ is a DR-
function, the number of super edges with property $(b)$ is at most
$\widehat{n}(G)$. This proves the inequality (1), and together with Theorem
2.2 we conclude

$\displaystyle\gamma_{\rm sp}(S_{k}(G))\geq
n(S_{k}(G))-\alpha^{\prime}(S_{k}(G))\geq\frac{k+1}{2}\,m(G)+(n(G)-\widehat{n}(G))$
(2)

where, according to Lemma 5.1, the last term is $1$ if $G$ is a tree and $0$
if $G$ contains a cycle.

To prove the other direction, we construct a $\gamma_{\rm sp}$-set $D$ for
$G$. Let $\phi$ be a DR-function of $G$ with domain $V(G)$ if $G$ is not a
tree, and with domain $V(G)\setminus\\{v_{n}\\}$ otherwise.

  * $(i)$

If $\phi(v_{i})=v_{i}v_{j}$, let $D$ contain the following vertices from the
super edge $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{1},(v_{i}v_{j})_{2},(v_{i}v_{j})_{5},(v_{i}v_{j})_{6},\dots,(v_{i}v_{j})_{4t+1},(v_{i}v_{j})_{4t+2}.$

  * $(ii)$

If $v_{i}v_{j}$ does not belong to the image set of $\phi$ and $i<j$, let $D$
contain the following vertices from the super edge $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{2},(v_{i}v_{j})_{3},(v_{i}v_{j})_{6},(v_{i}v_{j})_{7},\dots,(v_{i}v_{j})_{4t+2},(v_{i}v_{j})_{4t+3}.$

  * $(iii)$

If $G$ is a tree and $v_{n}$ does not have a representative edge in $\phi$,
then $v_{n}$ also belongs to $D$. Note that the other vertices of $G$ belong
to $\overline{D}$.

If an internal subdivision vertex, $(v_{i}v_{j})_{s}$ with $3\leq s\leq 4t+1$,
does not belong to $D$, it is easy to identify a neighbor that super dominates
it. A vertex $v_{i}$ with $\phi(v_{i})=v_{i}v_{j}$ is always super dominated
by $(v_{i}v_{j})_{1}$. The subdivision vertices $(v_{i}v_{j})_{2}$ and
$(v_{i}v_{j})_{4t+2}$ always belong to $D$; if $(v_{i}v_{j})_{1}\notin D$, it
is super dominated by $(v_{i}v_{j})_{2}$; if $(v_{i}v_{j})_{4t+3}\notin D$, it
is super dominated by $(v_{i}v_{j})_{4t+2}$.

No matter whether $(i)$ or $(ii)$ was applied when we specified the vertices
in $V(P_{v_{i}v_{j}})\cap D$, we added exactly $2t+2=\frac{k+1}{2}$
subdivision vertices to $D$ in each step. Thus, $D$ contains
$\frac{k+1}{2}\,m(G)$ subdivision vertices and also contains $v_{n}$ if $G$ is
a tree. This proves the upper bound

$\gamma_{\rm sp}(S_{k}(G))\leq\frac{k+1}{2}\,m(G)+(n(G)-\widehat{n}(G)).$

We infer that the equality $\gamma_{\rm
sp}(S_{k}(G))=\frac{k+1}{2}\,m(G)+(n(G)-\widehat{n}(G))$ holds for every graph
$G$ as stated. $\square$

For connected graphs, Theorem 5.2 and inequality (2) in its proof together
imply the following statement. Since $\gamma_{\rm sp}(F)$ and
$\alpha^{\prime}(F)$ are additive under disjoint union of graphs, we may
state:

###### Proposition 5.3

For every graph $G$ and integer $k\equiv 3\bmod 4$, it holds that

$\gamma_{\rm sp}(S_{k}(G))=n(S_{k}(G))-\alpha^{\prime}(S_{k}(G)).$

As the number of tree components in $G$ can be computed in linear time, and
$\gamma_{\rm sp}(F)$ is additive under taking disjoint union of graphs, we
conclude the subsection with the following consequence of Theorem 5.2.

###### Theorem 5.4

If $k$ is a positive integer with $k\equiv 3\bmod 4$, then the super
domination number can be computed in linear time over the class of
$k$-subdivision graphs.

###  5.2 $(4t+1)$-subdivisions

###### Theorem 5.5

For every connected graph $G$ and integer $k\equiv 1\bmod 4$,

$\gamma_{\rm
sp}(S_{k}(G))=\left\\{\begin{array}[]{ll}\frac{k+1}{2}\,m(G);&\mbox{$G$
contains an even cycle};\\\ \\\
\frac{k+1}{2}\,m(G)+1;&\mbox{otherwise}.\end{array}\right.$

Proof. Let $V(G)=\\{v_{1},\ldots,v_{n}\\}$ and $k=4t+1$. Suppose first that
$D$ is a minimum super dominating set of $S_{k}(G)$ and consider
$A=\overline{D}$ and a core $B$ of $D$. By Lemma 2.4, the edges $E[A,B]$ form
a matching $M$ in $S_{k}(G)$. If $M$ is fixed, we have three possibilities for
a super edge $P_{v_{i}v_{j}}$.

  * $(a)$

$M$ contains at most $\frac{k-1}{2}$ edges from $P_{v_{i}v_{j}}$. The set of
the corresponding edges $v_{i}v_{j}\in E(G)$ will be denoted by $E_{0}$.

  * $(b)$

$M$ contains exactly $\frac{k+1}{2}$ edges from $P_{v_{i}v_{j}}$ and exactly
one of $v_{i}$ and $v_{j}$ is covered by an edge from $M\cap
E(P_{v_{i}v_{j}})$. If this vertex, say $v_{i}$, is contained in $A$, we set
$v_{i}v_{j}\in E_{A}$. Similarly, if $v_{i}\in B$, $v_{i}(v_{i}v_{j})_{1}\in
M$, and $(v_{i}v_{j})_{k}v_{j}\notin M$, then the edge $v_{i}v_{j}$ belongs to
$E_{B}$.

  * $(c)$

$M$ contains exactly $\frac{k+1}{2}$ edges from $P_{v_{i}v_{j}}$ and both
$v_{i}(v_{i}v_{j})_{1}$ and $(v_{i}v_{j})_{k}v_{j}$ belong to $M$. In this
case, we set $v_{i}v_{j}\in E_{2}$.

As $E_{0},E_{A},E_{B},E_{2}$ is a partition of $E(G)$, we may estimate the
size of $M$ as follows:

$\displaystyle|M|\leq|E_{0}|\,\frac{k-1}{2}+(|E_{A}|+|E_{B}|+|E_{2}|)\,\frac{k+1}{2}=\frac{k-1}{2}\,m(G)+|E_{A}|+|E_{B}|+|E_{2}|.$
(3)

By definition, if $v_{i}v_{j}\in E_{A}\cup E_{B}$, then only one of
$v_{i}(v_{i}v_{j})_{1}$ and $(v_{i}v_{j})_{k}v_{j}$ belongs to $M$. If
$v_{i}v_{j}\in E_{2}$, then both $v_{i}(v_{i}v_{j})_{1}$ and
$(v_{i}v_{j})_{k}v_{j}$ are contained in $M$. Since each vertex $v_{i}\in
V(G)$ is covered by at most one $M$-edge, we infer
$|E_{A}|+|E_{B}|+2|E_{2}|\leq n$ and, in turn, we get from (3) that

$\displaystyle|M|\leq\frac{k-1}{2}\,m(G)+n-|E_{2}|.$ (4)

As $|M|=|A|=|\overline{D}|=n(S_{k}(G))-\gamma_{\rm sp}(S_{k}(G))$ and
$n(S_{k}(G))=n+k\,m(G)$, inequality (4) implies

$\displaystyle\gamma_{\rm
sp}(S_{k}(G))=n(S_{k}(G))-|M|\geq\frac{k+1}{2}\,m(G)+|E_{2}|.$ (5)

If $E_{2}\neq\emptyset$ or $G$ contains an even cycle, (5) itself proves the
required lower bound. From now on, we assume that there is no even cycle in
$G$ and that $E_{2}=\emptyset$.

Consider an edge $v_{i}v_{j}\in E_{A}$ with $v_{i}(v_{i}v_{j})_{1}\in M$. As
$M$ contains $\frac{k+1}{2}$ edges from $P_{v_{i},v_{j}}$ that includes
$v_{i}(v_{i}v_{j})_{1}$ but not $(v_{i}v_{j})_{k}v_{j}$, $M$ contains the
following edges from the super edge:

$v_{i}(v_{i}v_{j})_{1},(v_{i}v_{j})_{2}(v_{i}v_{j})_{3},\dots,(v_{i}v_{j})_{4t}(v_{i}v_{j})_{4t+1}.$

By Lemma 2.4, $v_{i}\in A$ implies $(v_{i}v_{j})_{1}\in B$; the latter implies
$(v_{i}v_{j})_{2}\in B$. Since $(v_{i}v_{j})_{2}(v_{i}v_{j})_{3}\in M$, we
infer $(v_{i}v_{j})_{3}\in A$; and so on. We obtain that $(v_{i}v_{j})_{s}\in
B$ if and only if $s\bmod 4\in\\{1,2\\}$; otherwise, $(v_{i}v_{j})_{s}\in A$.
In the last step, $v_{j}\in B$ also follows. It can be proved analogously that
$v_{i}v_{j}\in E_{B}$ and $v_{i}\in B$ implies $v_{j}\in A$.

Let

$V^{\prime}=\\{v_{i}:\exists j\in[n]\mbox{ s.t. }v_{i}(v_{i}v_{j})_{1}\in
M\\},\quad V^{\prime\prime}=\\{v_{j}:\exists i\in[n]\mbox{ s.t.
}v_{i}(v_{i}v_{j})_{1}\in M\\},$

and define a DR-function $\phi:V^{\prime}\to E_{A}\cup E_{B}$ such that
$\phi(v_{i})=v_{i}v_{j}$ if $v_{i}(v_{i}v_{j})_{1}\in M$. Since
$E_{2}=\emptyset$, it is an injective function. Moreover, if the edge
$v_{i}v_{j}$ is in the image of $\phi$, then one from $v_{i}$ and $v_{j}$
belongs to $A$ and the other one to $B$. Thus, $\phi$ remains a DR-function on
$V^{\prime}$, if we consider the following bipartite subgraph $F$ instead of
$G$. We first take the induced subgraph $G[V_{F}]$, where
$V_{F}=V^{\prime}\cup V^{\prime\prime}$, and then delete the edges inside
$V_{F}\cap A$ and $V_{F}\cap B$. We may also say that this graph $F$ is
defined by the edge set $E_{G}[V_{F}\cap A,V_{F}\cap B]$. By supposition, $G$
contains no even cycle. Therefore, the bipartite subgraph $F$ contains no
cycle at all. By Lemma 5.1, $\widehat{n}(F)\leq n(F)-1\leq n-1$. Consequently,
no more than $n-1$ vertices of $G$ are covered by an edge from $M$ in
$S_{k}(G)$. This implies $|E_{A}|+|E_{B}|\leq n-1$ and, by (3), we infer
$|M|\leq\frac{k-1}{2}\,m(G)+n-(n-1)$ that yields

$\gamma_{\rm sp}(S_{k}(G))\geq\frac{k+1}{2}\,m(G)+1,$

if $G$ contains no even cycle.

To prove the reverse inequalities, we construct a $\gamma_{\rm sp}$-set $D$
for $G$. First we define an appropriate DR-function $\phi$.

  * •

If $G$ contains an even cycle $C$, take a unicyclic spanning subgraph $H$ of
$G$ such that $C$ is the only cycle in $H$. Then $H$ is bipartite, not a tree,
and therefore, by Lemma 5.1, $\widehat{n}(H)=n$. Let $A_{H}$ and $B_{H}$ be
the partite classes of $H$. By Lemma 5.1, there is a DR-function $\phi$ which
assigns a representative edge from $E(H)$ to each vertex from $V(G)$.

  * •

If $G$ contains no even cycle, choose a spanning tree $H$ in $G$. Again, $H$
is bipartite, but now we have $\widehat{n}(H)=n-1$. Let $A_{H}$ and $B_{H}$ be
the partite classes of $H$. By Lemma 5.1, we can define a DR-function $\phi$
that assigns a representative edge from $E(H)$ to each vertex from
$V(G)\setminus\\{v_{n}\\}$.

Having a DR-function $\phi$ in hand, we define a super dominating set $D$ in
$S_{k}(G)$ with a size that matches the required upper bound.

  * $(i)$

If $v_{i}\in B_{H}$ or $v_{i}\notin A_{H}\cup B_{H}$, we set $v_{i}\in D$.

  * $(ii)$

If $\phi(v_{i})=v_{i}v_{j}$ and $v_{i}\in A_{H}$, let $D$ contain the
following vertices from the super edge $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{1},(v_{i}v_{j})_{2},(v_{i}v_{j})_{5},(v_{i}v_{j})_{6},\dots,(v_{i}v_{j})_{4t-3},(v_{i}v_{j})_{4t-2},(v_{i}v_{j})_{4t+1}.$

  * $(iii)$

If $\phi(v_{i})=v_{i}v_{j}$ and $v_{i}\in B_{H}$, let $D$ contain the
following vertices from $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{3},(v_{i}v_{j})_{4},(v_{i}v_{j})_{7},(v_{i}v_{j})_{8},\dots,(v_{i}v_{j})_{4t-1},(v_{i}v_{j})_{4t}.$

  * $(iv)$

If $v_{i}v_{j}$ does not belong to the image set of $\phi$, $v_{i}\in A_{H}$,
and $i<j$, then let $D$ contain the following vertices from $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{2},(v_{i}v_{j})_{3},(v_{i}v_{j})_{6},(v_{i}v_{j})_{7},\dots,(v_{i}v_{j})_{4t-2},(v_{i}v_{j})_{4t-1},(v_{i}v_{j})_{4t+1}.$

  * $(v)$

If $v_{i}v_{j}$ does not belong to the image set of $\phi$, $v_{i}\in B_{H}$,
and $i<j$, let $D$ contain the following vertices from $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{1},(v_{i}v_{j})_{4},(v_{i}v_{j})_{5},(v_{i}v_{j})_{8},(v_{i}v_{j})_{9},\dots,(v_{i}v_{j})_{4t},(v_{i}v_{j})_{4t+1}.$

If an internal subdivision vertex, $(v_{i}v_{j})_{s}$ with $3\leq s\leq 4t-1$,
does not belong to $D$, it is easy to see that a neighbor super dominates it.
A vertex $v_{i}\notin D$ with $\phi(v_{i})=v_{i}v_{j}$ is always super
dominated by $(v_{i}v_{j})_{1}$. The subdivision vertex $u=(v_{i}v_{j})_{1}$
does not belong to $D$, if $(iii)$ or $(iv)$ was applied. In the latter case,
$(v_{i}v_{j})_{2}$ super dominates $u$. In the first case, $v_{i}\in B_{H}$
and $(N[v_{i}]\setminus\\{u\\})\subseteq D$ holds by the determination of $D$.
The subdivision vertex $w=(v_{i}v_{j})_{2}$ is missing from $D$, if $(iii)$ or
$(v)$ was applied. In the first case, $(v_{i}v_{j})_{3}$ super dominates $w$.
For the second case, the condition in $(v)$ ensures that $v_{i}\in D$. Hence,
$w$ is the only neighbor of $(v_{i}v_{j})_{1}$ which is outside $D$. In case
$(ii)$, vertex $(v_{i}v_{j})_{4t}$ is super dominated by $(v_{i}v_{j})_{4t+1}$
as in this case $v_{i}\in A_{H}$ implies $v_{j}\in B_{H}$ and therefore, we
have $v_{j}\in D$. In case $(iv)$, vertex $(v_{i}v_{j})_{4t}$ is super
dominated by $(v_{i}v_{j})_{4t-1}.$ A vertex $(v_{i}v_{j})_{4t+1}$ is outside
$D$, only if $(iii)$ was applied. In this case, $(v_{i}v_{j})_{4t}$ super
dominates it.

Finally, we determine the size of $D$. Case $(i)$ puts $n-|A_{H}|$ vertices
into $D$. When the subdivision vertices are considered, we put $\frac{k+1}{2}$
vertices from each $P_{i,j}$ into $D$, except when case $(iii)$ is applied.
There we deal with $|B_{H}|$ super edges putting $\frac{k-1}{2}$ internal
vertices into $D$ from each. This gives

$\gamma_{\rm sp}(S_{k}(G))\leq|D|=n-|A_{H}|+m(G)\,\frac{k+1}{2}-|B_{H}|.$

By the determination of the DR-function $\phi$, $|A_{H}|+|B_{H}|=n$ if $G$
contains an even cycle; and $|A_{H}|+|B_{H}|=n-1$ if every cycle in $G$ is of
odd order. Substituting these values in the inequality, we get the required
upper bounds on $\gamma_{\rm sp}(S_{k}(G))$. This finishes the proof of the
theorem. $\square$

Let $\mbox{oc}(G)$ denote the number of components in $G$ that contain no even
cycles. Then Theorem 5.5 directly implies:

###### Proposition 5.6

For every graph $G$ and integer $k\equiv 1\bmod 4$, it holds that

$\gamma_{\rm sp}(S_{k}(G))=\frac{k+1}{2}m(G)+\mbox{oc}(G).$

A shortest even cycle in a graph can be found in polynomial (actually
quadratic) time [24], hence the number of even-cycle-free components is easy
to determine. Thus we may deduce the following result:

###### Theorem 5.7

If $k$ is a positive integer with $k\equiv 1\bmod 4$, then the super
domination number can be computed in polynomial time over the class of
$k$-subdivision graphs.

###  5.3 $4t$-subdivisions

###### Theorem 5.8

For every graph $G$ and integer $k\equiv 0\bmod 4$,

$\gamma_{\rm sp}(S_{k}(G))=\frac{k}{2}\,m(G)+\gamma_{\rm sp}(G).$

Proof. Let $V(G)=\\{v_{1},\ldots,v_{n}\\}$ and $k=4t$. Suppose that $D$ is a
$\gamma_{\rm sp}$-set of $S_{k}(G)$ and consider $A=\overline{D}$ and a core
$B$ of $D$. By Lemma 2.4, the edges $E[A,B]$ form a matching $M$ in
$S_{k}(G)$. We have three possibilities for a super edge $P_{v_{i}v_{j}}$.

  * $(a)$

$M$ contains at most $\frac{k}{2}-1$ edges from $P_{v_{i}v_{j}}$. Let $E_{0}$
denote the set of the edges $v_{i}v_{j}\in E(G)$ with this property.

  * $(b)$

$M$ contains exactly $\frac{k}{2}$ edges from $P_{v_{i}v_{j}}$. The set of the
corresponding edges $v_{i}v_{j}$ in $G$ is denoted by $E_{1}$.

  * $(c)$

$M$ contains exactly $\frac{k}{2}+1$ edges from $P_{v_{i}v_{j}}$. In this
case, both $v_{i}(v_{i}v_{j})_{1}$ and $(v_{i}v_{j})_{k}v_{j}$ belong to $M$,
and we set $v_{i}v_{j}\in E_{2}$.

By definitions given for $E_{0},E_{1},E_{2}$, the following is true:

$\displaystyle|M|\leq\frac{k}{2}\,m(G)+|E_{2}|-|E_{0}|.$ (6)

To prove that $|E_{2}|-|E_{0}|\leq n-\gamma_{\rm sp}(G)$, we first consider a
super edge $P_{v_{i}v_{j}}$ so that $v_{i}v_{j}\in E_{2}$. The edges

$v_{i}(v_{i}v_{j})_{1},(v_{i}v_{j})_{2}(v_{i}v_{j})_{3},\dots,(v_{i}v_{j})_{4t-2}(v_{i}v_{j})_{4t-1},(v_{i}v_{j})_{4t}v_{j}$

are all included in $M$. If $v_{i}\in A$ then, by Lemma 2.4, $E[A,B]$ is a
matching and the vertices

$(v_{i}v_{j})_{1},(v_{i}v_{j})_{2},(v_{i}v_{j})_{5},(v_{i}v_{j})_{6},\dots,(v_{i}v_{j})_{4t-2},v_{j}$

are from $B$; while the remaining subdivision vertices belong to $A$.
Therefore, $v_{i}\in A$ implies $v_{j}\in B$ and, similarly, $v_{i}\in B$
implies $v_{j}\in A$.

If $v_{i}v_{j}\in E_{2}$, $v_{p}v_{q}\in E_{2}$ with $v_{i}\in A$, $v_{q}\in
B$, and $G$ contains an edge $v_{i}v_{q}$, then we say that $v_{i}v_{q}$ is a
_critical edge_. As $v_{i}$ and $v_{q}$ are already covered by $M$-edges,
$v_{i}v_{q}\notin E_{2}$. If $v_{i}v_{q}\in E_{1}$, then the $k/2$ edges in
$M\cap E(P_{v_{i}v_{q}})$ have to be

$(v_{i}v_{q})_{1}(v_{i}v_{q})_{2},(v_{i}v_{q})_{3}(v_{i}v_{q})_{4},\dots,(v_{i}v_{q})_{k-1}(v_{i}v_{q})_{k}.$

By Lemma 2.4, $v_{i}\in A$ implies $(v_{i}v_{q})_{1}\in A$,
$(v_{i}v_{q})_{2},(v_{i}v_{q})_{3}\in B$,
$(v_{i}v_{q})_{4},(v_{i}v_{q})_{5}\in A,\dots,(v_{i}v_{q})_{k}\in A$. Finally,
we infer $v_{q}\in A$ that contradicts the assumption $v_{q}\in B$. It implies
that $v_{i}v_{q}\in E_{0}$. By symmetry, the same is true if $v_{i}\in B$ and
$v_{q}\in A$ and therefore, every critical edge belongs to $E_{0}$.

We now prove that the maximum for $|E_{2}|-|E_{0}|$ can be attained without
the presence of critical edges. Indeed, if $v_{i}v_{q}$ is a critical edge
such that $v_{i}v_{j},v_{p}v_{q}\in E_{2}$ and $v_{i}\in A$, $v_{q}\in B$,
then we may perform the following changes in $M$:

  * •

Remove the edges $M\cap E(P_{v_{i},v_{j}})$ from $M$ and replace them by the
complement edge set $E(P_{v_{i},v_{j}})\setminus M$. By this change,
$v_{i}v_{j}$ is moved to $E_{1}$, and $v_{i},v_{j}$ become uncovered by $M$.
So, this step decreases $|E_{2}|$ by $1$. After this change $v_{i}\notin A\cup
B$ and we can replace the (at most) $\frac{k}{2}-1$ $M$-edges on
$P_{v_{i},v_{q}}$ with the following $\frac{k}{2}$ edges:

$(v_{i}v_{q})_{1}(v_{i}v_{q})_{2},(v_{i}v_{q})_{3}(v_{i}v_{q})_{4},\dots,(v_{i}v_{q})_{4t-1}(v_{i}v_{q})_{4t}$

such that we put
$(v_{i}v_{q})_{1},(v_{i}v_{q})_{4},(v_{i}v_{q})_{5},\dots,(v_{i}v_{q})_{4t}$
into $B$ and the remaining subdivision vertices into $A$. Since $v_{q}\in B$,
this step keeps the property $E[A,B]=M$ and, by Lemma 2.4, $D=\overline{A}$ is
a super dominating set in $S_{k}(G)$. Note that this modification removes
$v_{i}v_{q}$ from $E_{0}$.

After applying the described changes, $|E_{2}|-|E_{0}|$ remains the same and
we have less critical edges than before. Thus, performing the steps
iteratively while there is a critical edge, we obtain a matching $M^{\prime}$
and sets $A^{\prime},B^{\prime}$ without critical edges such that
$|E_{2}|-|E_{0}|$ remains unchanged. As there are no critical edges, the
$E_{2}$-edges now form a matching $M^{*}$ in $G$ such that
$E[A^{*},B^{*}]=M^{*}$ for the sets $A^{*}=A^{\prime}\cap V(G)$ and
$B^{*}=B^{\prime}\cap V(G)$. Applying Lemma 2.4 again, we conclude that
$D^{*}=\overline{A^{*}}$ is a super dominating set in $G$. This yields

$|E_{2}|=|M^{*}|=|A^{*}|=n-|D^{*}|\leq n-\gamma_{\rm sp}(G).$

Now inequality chain in (6) can be continued and we obtain

$|M|\leq\frac{k}{2}\,m(G)+|E_{2}|-|E_{0}|\leq\frac{k}{2}\,m(G)+n-\gamma_{\rm
sp}(G)$

which, in turn, proves

$\displaystyle\gamma_{\rm sp}(S_{k}(G))$ $\displaystyle=n(S_{k}(G))-|M|$
$\displaystyle\geq\left(n+k\,m(G)\right)-\left(\frac{k}{2}\,m(G)+n-\gamma_{\rm
sp}(G)\right)$ $\displaystyle=\frac{k}{2}\,m(G)+\gamma_{\rm sp}(G).$

In the second part of the proof we construct a super dominating set $D$ of
size $\frac{k}{2}\,m(G)+\gamma_{\rm sp}(G)$ in $S_{k}(G)$. Let $D^{*}$ be a
$\gamma_{\rm sp}$-set in $G$ with the corresponding sets $A^{*},B^{*}$ and
matching $M^{*}=E_{G}[A^{*},B^{*}]$.

  * $(i)$

If $v_{i}\in D^{*}$, we set $v_{i}\in D$.

  * $(ii)$

If $v_{i}v_{j}\in M^{*}$ with $v_{i}\in A^{*}$ and $v_{j}\in B^{*}$, let $D$
contain the following vertices from the super edge $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{1},(v_{i}v_{j})_{2},(v_{i}v_{j})_{5},(v_{i}v_{j})_{6},\dots,(v_{i}v_{j})_{4t-3},(v_{i}v_{j})_{4t-2}.$

  * $(iii)$

If $v_{i}v_{j}\notin M^{*}$ and $v_{i}\in A^{*}$ then, as
$E_{G}[A^{*},B^{*}]=M^{*}$, we have $v_{j}\in V(G)\setminus B^{*}$. Let us put
into $D$ the following subdivision vertices from $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{2},(v_{i}v_{j})_{3},(v_{i}v_{j})_{6},(v_{i}v_{j})_{7},\dots,(v_{i}v_{j})_{4t-2},(v_{i}v_{j})_{4t-1}.$

  * $(iv)$

If $v_{i}v_{j}\notin M^{*}$ and $v_{i}\in B^{*}$ hold and also if both $v_{i}$
and $v_{j}$ are outside $A^{*}\cup B^{*}$, we put into $D$ the following
subdivision vertices from $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{1},(v_{i}v_{j})_{4},(v_{i}v_{j})_{5},\dots,(v_{i}v_{j})_{4t-4},(v_{i}v_{j})_{4t-3},(v_{i}v_{j})_{4t}.$

In step $(i)$, we put $|D^{*}|=\gamma_{\rm sp}(G)$ non-subdivision vertices
into $D$. Then, for each super edge considered in $(ii)-(iv)$, we put exactly
$k/2$ subdivision vertices into $D$. As there are no edge $v_{i}v_{j}$ in $G$
with $v_{i}\in A^{*}$, $v_{j}\in B^{*}$ and $v_{i}v_{j}\notin M^{*}$, we
treated each super edge of $S_{k}(G)$ in the steps $(ii)-(iv)$. These sum up
$|D|=\frac{k}{2}\,m(G)+\gamma_{\rm sp}(G)$.

To check that $D$ is a super dominating set is mainly automatic. We note that
if $v_{i}\notin D$, then $v_{i}\in A^{*}$ and there is an edge $v_{i}v_{j}\in
M^{*}$ which is considered in $(ii)$. Then, $(v_{i}v_{j})_{1}$ super dominates
$v_{i}$. We also remark that in step $(ii)$, the vertex $(v_{i}v_{j})_{4t}$ is
super dominated by $v_{j}$ as all the other super edges $P_{v_{j}v_{p}}$ being
incident to $v_{j}$ were considered in step $(iv)$. There, subdivision
neighbors $(v_{j}v_{p})_{1}=(v_{p}v_{j})_{4t}$ were put into $D$. For a super
edge $P_{v_{i}v_{j}}$ that was treated in $(iv)$, the condition implies
$v_{i},v_{j}\in D$. Therefore, $(v_{i}v_{j})_{1}$ and $(v_{i}v_{j})_{4t}$
super dominate $(v_{i}v_{j})_{2}$ and $(v_{i}v_{j})_{4t-1}$, respectively. It
shows $\gamma_{\rm sp}(S_{k}(G))\leq|D|=\frac{k}{2}\,m(G)+\gamma_{\rm sp}(G)$,
and together with the first part of the proof give the equality $\gamma_{\rm
sp}(S_{k}(G))=\frac{k}{2}\,m(G)+\gamma_{\rm sp}(G)$ as required. $\square$

The problem of deciding whether $\gamma_{\rm sp}(F)\leq\ell$ holds, clearly
belongs to NP. Let $\ell$ be part of the input of the problem and $k$ be a
fixed integer with $k\equiv 0\bmod 4$. By Theorem 4.1, it is NP-hard to decide
whether $\gamma_{\rm sp}(G)\leq\ell$ holds over the class of all graphs. By
Theorem 5.8, $\gamma_{\rm sp}(G)\leq\ell$ holds if and only if $\gamma_{\rm
sp}(S_{k}(G))\leq\frac{k}{2}\,m(G)+\ell$. Thus, we may conclude the following:

###### Theorem 5.9

Over the class of $k$-subdivision graphs, it is NP-complete to decide whether
$\gamma_{\rm sp}(F)\leq\ell$ holds, if $\ell$ is part of the input and $k$ is
a fixed integer with $k\equiv 0\bmod 4$.

###  5.4 II-matchings

Before continuing our study with the last case for subdivision graphs, we
introduce a graph invariant and prove an additional complexity result.

In a graph $G$, an _induced matching_ is a matching $M\subseteq E(G)$ such
that the induced subgraph $G[V(M)]$ contains only the edges from $M$. We
denote by $i(G)$ the maximum size of an induced matching in $G$. Induced
matchings are applicable in network flow problems, secure communication, VLSI
design, and elsewhere, cf. [7, 19]. To decide whether $i(G)\geq\ell$ holds is
known to be NP-hard in many classes of graphs, say in planar bipartite graphs
[21] and in claw-free graphs [15]. For exact algorithms for maximum induced
matchings see [18, 23], and for the complexity aspects of the maximum-weight
induced matchings and dominating induced matchings see [13, 4], respectively,
and references therein.

We further say that a matching $M$ is an _II-matching_ if $M$ can be
partitioned into two induced matchings $M_{1}$ and $M_{2}$. The _II-matching
number_ $\mbox{ii}(G)$ of $G$ is the maximum size of an II-matching in $G$. We
prove that the II-matching number is hard to determine.

###### Proposition 5.10

It is NP-complete to decide whether $\mbox{ii}(G)\geq\ell$ holds, if $\ell$ is
part of the input.

Proof. To decide whether the independence number $\alpha(F)$ of a graph $F$ is
at least $k$ is a classical NP-complete problem [10]. We show a polynomial-
time reduction from the decision problem of $\alpha(F)\geq k$ to the problem
of $\mbox{ii}(G)\geq 2k$.

#### Construction.

For every graph $F$, let $G_{F}$ be the graph constructed on the vertex set
$V(G)\times V(K_{4})$, where $V(K_{4})=[4]$, by making two different vertices
$(x,i)$ and $(y,j)$ adjacent in $G_{F}$ if either $xy\in E(F)$ or $x=y$. (We
note in passing that $G_{F}$ is isomorphic to the lexicographic product
$F\circ K_{4}$.) Let $V(F)=\\{v_{1},\dots,v_{n}\\}$ and let $V_{i}$ denote the
vertex set $\\{v_{i}\\}\times[4]$ in $G_{F}$.

#### Reduction.

We show that $\mbox{ii}(G_{F})=2\alpha(F)$ holds for every graph $F$ and
therefore, deciding whether $\alpha(F)\geq k$ is equivalent to the problem of
whether $\mbox{ii}(G_{F})\geq 2k$ holds.

First, consider a maximum independent set $S$ in $F$ and define the edge sets

$M_{1}=\\{(x,1)(x,2):x\in S\\}\quad\mbox{and}\quad M_{2}=\\{(x,3)(x,4):x\in
S\\}.$

By definition, $|M_{1}|=|M_{2}|=\alpha(F)$, $M_{1}\cup M_{2}$ is a matching in
$G_{F}$ and, since $S$ is an independent set in $F$, both $M_{1}$ and $M_{2}$
are induced matchings. It follows that $\mbox{ii}(G_{F})\geq 2\alpha(F)$.

Assume now, that we have a maximum II-matching $M=M_{1}\cup M_{2}$ in $G_{F}$.
If the induced matching $M_{1}$ contains a _cross edge_ $xy$, that is an edge
$xy$ with $x\in V_{i}$, $y\in V_{j}$ such that $i\neq j$, then $M_{1}$ cannot
cover any other vertex from the neighborhood of $x$. Equivalently, if
$v_{i}v_{i^{\prime}}$ is an edge in $F$, then $V_{i^{\prime}}\cap V(M_{1})$
cannot contain a vertex different from $y$. Thus, if the cross edge $xy$ is
replaced in $M_{1}$ with an arbitrary edge inside $V_{i}$, the set $M_{1}$
remains an induced matching. As $M_{2}$ is also an induced matching, it covers
at most two vertices from $V_{i}$. We therefore have a vertex $x^{\prime}\in
V_{i}$ such that $(M\setminus\\{xy\\})\cup\\{xx^{\prime}\\}$ is an II-matching
and $|M|=|M^{\prime}|$. Repeating this procedure for all cross edges in
$M_{1}\cup M_{2}$, we obtain an II-matching without cross edges. Again, we may
refer to the property that if $V_{i}$ contains an edge from $M_{p}$, for
$p\in[2]$, then $V(M_{p})\cap V_{i^{\prime}}=\emptyset$ whenever
$v_{i}v_{i^{\prime}}\in E(F)$. We may conclude that $|M_{p}|\leq\alpha(F)$ and
hence, $|M|\leq 2\alpha(F)$. This finishes the proof for
$\mbox{ii}(G_{F})=2\alpha(F)$.

#### Conclusion.

As $G_{F}$ is obtained by a polynomial-time construction from $F$, and the NP-
complete problem of deciding whether $\alpha(F)\geq k$ holds can be reduced to
the problem of deciding about $\mbox{ii}(G_{F})\geq 2k$, the latter problem is
also NP-hard. It is also clear that the decision problem of
$\mbox{ii}(G)\geq\ell$ belongs to NP. Thus, we may infer that the problem is
NP-complete over the class of all graphs. $\square$

###  5.5 $(4t+2)$-subdivisions

###### Theorem 5.11

For every graph $G$ and integer $k\equiv 2\bmod 4$,

$\gamma_{\rm sp}(S_{k}(G))=\frac{k}{2}\,m(G)+n(G)-\mbox{ii}(G).$

Proof. Let $V(G)=\\{v_{1},\ldots,v_{n}\\}$, and $k=4t+2$. Choose a
$\gamma_{\rm sp}$-set $D$ of $S_{k}(G)$. Let $A=\overline{D}$ and $B$ an
arbitrary core of $D$. By Lemma 2.4, the edges $E[A,B]$ form a matching $M$ in
$S_{k}(G)$. Again, we have three possibilities for a super edge
$P_{v_{i}v_{j}}$.

  * $(a)$

$M$ contains at most $\frac{k}{2}-1$ edges from $P_{v_{i}v_{j}}$. Let $E_{0}$
denote the set of the edges $v_{i}v_{j}\in E(G)$ with this property.

  * $(b)$

$M$ contains exactly $\frac{k}{2}$ edges from $P_{v_{i}v_{j}}$. The set of the
corresponding edges $v_{i}v_{j}$ in $G$ is denoted by $E_{1}$.

  * $(c)$

$M$ contains exactly $\frac{k}{2}+1$ edges from $P_{v_{i}v_{j}}$. In this
case, both $v_{i}(v_{i}v_{j})_{1}$ and $(v_{i}v_{j})_{k}v_{j}$ belong to $M$,
and we set $v_{i}v_{j}\in E_{2}$.

By definitions, the following inequality holds:

$\displaystyle|M|\leq\frac{k}{2}\,m(G)+|E_{2}|-|E_{0}|.$ (7)

For every edge $v_{i}v_{j}\in E_{2}$ of $G$, the super edge $P_{v_{i}v_{j}}$
must contain the edges
$v_{i}(v_{i}v_{j})_{1},(v_{i}v_{j})_{2}(v_{i}v_{j})_{3},\dots,(v_{i}v_{j})_{4t}v_{j}$
from $M$. Moreover, if $v_{i}\in A$ in $S_{k}(G)$ then, by Lemma 2.4, $E[A,B]$
is a matching in $S_{k}(G)$ and

$B\cap
V(P_{v_{i}v_{j}})=\\{(v_{i}v_{j})_{1},(v_{i}v_{j})_{2},(v_{i}v_{j})_{5},(v_{i}v_{j})_{6},\dots,(v_{i}v_{j})_{4t+1},(v_{i}v_{j})_{4t+2}\\}.$

The remaining subdivision vertices and $v_{j}$ then belong to $A$. Therefore,
$v_{i}\in A$ implies $v_{j}\in A$ and, similarly, $v_{i}\in B$ implies
$v_{j}\in B$ if $v_{i}v_{j}\in E_{2}$. We may therefore partition $E_{2}$ into

$E_{A}=\\{v_{i}v_{j}:v_{i}v_{j}\in E_{2}\mbox{ and }v_{i},v_{j}\in
A\\}\quad\mbox{and}\quad E_{B}=\\{v_{i}v_{j}:v_{i}v_{j}\in E_{2}\mbox{ and
}v_{i},v_{j}\in B\\}.$

Suppose now that $E_{A}$ contains two edges $v_{i}v_{j}$ and $v_{p}v_{q}$ and
there exists an edge $v_{i}v_{q}\in E(G)$. We will say that $v_{i}v_{q}$ is an
_$A$ -critical edge_. As $v_{i}$ and $v_{q}$ are already covered by $M$-edges,
$v_{i}v_{q}\notin E_{2}$. By the same reason, if $v_{i}v_{q}\in E_{1}$, then
the $k/2$ edges in $M\cap E(P_{v_{i}v_{q}})$ are
$(v_{i}v_{q})_{1}(v_{i}v_{q})_{2},\dots,(v_{i}v_{q})_{4t+1}(v_{i}v_{q})_{4t+2}.$
Referring to Lemma 2.4 again, $v_{i}\in A$ implies $(v_{i}v_{q})_{1}\in A$,
$(v_{i}v_{q})_{2},(v_{i}v_{q})_{3}\in B,\dots,(v_{i}v_{q})_{4t+2}\in B$, and
also that $v_{q}\in B$. As $v_{q}\in A$ was supposed, it is a contradiction.
We may infer that $v_{i}v_{q}\in E_{0}$ holds for every $A$-critical edge. The
same is true for the set $B$; that is if $v_{i}v_{j},v_{p}v_{q}\in E_{B}$ and
a $B$-critical edge $v_{i}v_{q}$ is present in $G$, then $v_{i}v_{q}\in
E_{0}$.

We now prove that the maximum for $|E_{2}|-|E_{0}|$ can be attained without
the presence of $A$\- and $B$-critical edges. Indeed, let $v_{i}v_{q}$ be an
$A$-critical edge such that $v_{i}v_{j},v_{p}v_{q}\in E_{A}$. We may perform
the following alteration in $M$ without decreasing $|E_{2}|-|E_{0}|$. First we
remove the edges $M\cap E(P_{v_{i},v_{j}})$ from $M$ and replace them by the
complement edge set $E(P_{v_{1},v_{j}})\setminus M$. Then, we also remove the
at most $\frac{k}{2}-1$ edges $M\cap E(P_{v_{i}v_{q}})$ and replace them by
the $\frac{k}{2}$ edges
$(v_{i}v_{q})_{1}(v_{i}v_{q})_{2},\dots,(v_{i}v_{q})_{4t+1}(v_{i}v_{q})_{4t+2}$.
After these changes we update the sets $A$ and $B$ along $P_{v_{i}v_{j}}$ and
$P_{v_{i}v_{q}}$ such that, for $x\in\\{j,q\\}$ and $s\in[4t+2]$, a
subdivision vertex $(v_{i}v_{x})_{s}$ belongs to $B$ if $s\bmod
4\in\\{0,1\\}$, otherwise it is put into $A$. The vertices $v_{i}$, $v_{j}$
are not in $A$ anymore, but we still have $v_{q}\in A$. It can be checked that
$E[A,B]$ remains a matching and, by Lemma 2.4, $D=\overline{A}$ is a super
dominating of $S_{k}(G)$. By this change, both $v_{i}v_{j}$ and $v_{i}v_{q}$
are moved to $E_{1}$, the number of $A$-critical edges is decreased, while
$|E_{2}|-|E_{0}|$ remains the same. By the symmetry of the roles of the sets
$A$ and $B$, if a $B$-critical edge exists, we may do the analogous changes.

Repeating these changes while there are critical edges, we obtain a matching
$M$ and a super dominating set $D$ without decreasing $|E_{2}|-|E_{0}|$. The
edges in $E_{2}$ still form a matching as every $u\in V(G)$ is covered only
one edge from $M$; and the absence of $A$\- and $B$-critical edges means that
both $E_{A}$ and $E_{B}$ are induced matchings in $G$. It implies that the
obtained $M$ is an II-matching and hence, $|E_{2}|\leq\mbox{ii}(G)$. From (7),
we now obtain

$|M|\leq\frac{k}{2}\,m(G)+\mbox{ii}(G),$

and we may conclude

$\displaystyle\gamma_{\rm sp}(S_{k}(G))$
$\displaystyle=n(S_{k}(G))-|M|\geq\frac{k}{2}\,m(G)+n(G)-\mbox{ii}(G).$ (8)

To complete the proof, we show that there exists a super dominating set $D$ of
the required cardinality in $S_{k}(G)$. Let $M^{*}=M^{*}_{1}\cup M^{*}_{2}$ be
a maximum II-matching in $G$. The set $D$ is constructed by the following five
rules.

  * $(i)$

A vertex $v_{i}\in V(G)$ belongs to $D$ if and only if $v_{i}\notin
V(M_{1}^{*})$.

  * $(ii)$

If $v_{i}v_{j}\in M^{*}_{1}$, then $D$ contains the following vertices from
the super edge $P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{1},(v_{i}v_{j})_{2},(v_{i}v_{j})_{5},(v_{i}v_{j})_{6},\dots,(v_{i}v_{j})_{4t+1},(v_{i}v_{j})_{4t+2}.$

  * $(iii)$

If $v_{i}v_{j}\in M^{*}_{2}$, then $D$ contains the following vertices from
$P_{v_{i}v_{j}}$:

$(v_{i}v_{j})_{3},(v_{i}v_{j})_{4},(v_{i}v_{j})_{7},(v_{i}v_{j})_{8},\dots,(v_{i}v_{j})_{4t-1},(v_{i}v_{j})_{4t}.$

  * $(iv)$

If $v_{i}v_{j}\notin M^{*}$ and $v_{i}\in V(M_{1}^{*})$, then $v_{j}\notin
V(M_{1}^{*})$. In this case, we put the following subdivision vertices into
$D$:

$(v_{i}v_{j})_{2},(v_{i}v_{j})_{3},(v_{i}v_{j})_{6},(v_{i}v_{j})_{7},\dots,(v_{i}v_{j})_{4t-2},(v_{i}v_{j})_{4t-1},(v_{i}v_{j})_{4t+2}.$

  * $(v)$

If $v_{i}v_{j}\notin M^{*}$ and $v_{i}\in V(M_{2}^{*})$, $v_{j}\notin
V(M^{*})$, and also if $v_{i},v_{j}\notin V(M^{*})$, we put the following
subdivision vertices into $D$:

$(v_{i}v_{j})_{1},(v_{i}v_{j})_{4},(v_{i}v_{j})_{5},\dots,(v_{i}v_{j})_{4t},(v_{i}v_{j})_{4t+1}.$

In step $(i)$ we put $n(G)-2|M_{1}^{*}|$ non-subdivision vertices into $D$; in
step $(ii)$ we consider $|M_{1}^{*}|$ super edges and put $\frac{k+2}{2}$
subdivision vertices from each into $D$; in $(iii)$ $|M_{2}^{*}|$ super edges
are considered and put $|M_{2}^{*}|\,\frac{k+2}{2}$ vertices into $D$. For the
remaining edges $v_{i}v_{j}$ of $G$ step $(iv)$ or $(v)$ is applied. In either
case, $D$ contains exactly $\frac{k}{2}$ subdvision vertices from
$P_{v_{i}v_{j}}$. The size of $D$ is therefore

$\displaystyle|D|$
$\displaystyle=(n(G)-2|M_{1}^{*}|)+|M_{1}^{*}|\left(\frac{k}{2}+1\right)+|M_{2}^{*}|\left(\frac{k}{2}-1\right)+(m(G)-|M_{1}^{*}|-|M_{2}^{*}|)\,\frac{k}{2}$
$\displaystyle=\frac{k}{2}\,m(G)+n(G)-(|M_{1}^{*}|+|M_{2}^{*}|)$
$\displaystyle=\frac{k}{2}\,m(G)+n(G)-\mbox{ii}(G).$

It is straightforward to check that $D$ is a super dominating set in
$S_{k}(G)$. We notice that if a vertex $v_{i}\in V(G)$ does not belong to $D$,
then there exists an edge $v_{i}v_{j}\in M_{1}^{*}$ and, by $(ii)$, the
subdivision vertex $(v_{i}v_{j})_{1}$ super dominates $v_{i}$. If $v_{i}\in
V(M_{2}^{*})$ such that $v_{i}v_{j}\in M_{2}^{*}$, then $v_{i}\in D$ and
$(v_{i}v_{j})_{1}$ is $v_{i}$’s only neighbor which is not in $D$. Then,
$v_{i}$ super dominates $(v_{i}v_{j})_{1}$ (that is the same as
$(v_{j}v_{i})_{4t+2}$.) For a super edge $P_{v_{i}v_{j}}$ considered in $(v)$,
both ends $v_{i}$ and $v_{j}$ belong to $D$ and hence, $(v_{i}v_{j})_{1}$
super dominates $(v_{i}v_{j})_{2}$.

Since the constructed set $D$ is a super dominating set, we may conclude

$\gamma_{\rm sp}(S_{k}(G))\leq|D|=\frac{k}{2}\,m(G)+n(G)-\mbox{ii}(G)$

which, together with (8), complete the proof of the theorem. $\square$

As a consequence of Proposition 5.10 and Theorem 5.11, we obtain the following
result.

###### Theorem 5.12

Over the class of $k$-subdivision graphs, it is NP-complete to decide whether
$\gamma_{\rm sp}(F)\leq\ell$ holds, if $\ell$ is part of the input and $k$ is
a fixed integer with $k\equiv 2\bmod 4$.

##  6 Conclusions

We conclude the paper by summarizing our main results on the computational
complexity of the following problem.

SUPER DOMINATION (S-DOM) PROBLEM Instance: A simple undirected graph $G$ and
an integer $\ell$. Question: Does $\gamma_{\rm sp}(G)\leq\ell$ hold?

By Theorems 3.1, 4.1, 5.4, 5.7, 5.9, and 5.12, we can conclude the following
summary.

• The S-DOM problem is NP-complete over the following graph classes: (A)
Bipartite graphs of girth at least $8$; (B) Class of $k$-subdivision graphs if
$k$ is a fixed even integer. • The S-DOM problem can be solved in polynomial
time over the following graph classes: (C) Trees; (D) Class of $k$-subdivision
graphs if $k$ is an odd integer.

Classes (A), (C), and (D) are subclasses of bipartite graphs. However, to get
a better picture of the computational complexity of the S-DOM problem on the
class of bipartite graphs, we propose the following problems.

###### Problem 6.1

Find a subclass ${\cal C}$ of (A) so that the S-DOM problem remains NP-
complete on ${\cal C}$.

###### Problem 6.2

Find further subclasses of bipartite graphs over which the S-DOM problem can
be solved in polynomial time.

The ultimate goal we set is a complete characterization:

###### Problem 6.3

Characterize the subclasses of bipartite graphs over which the S-DOM problem
remains NP-complete.

## Acknowledgments

Nima Ghanbari would like to thank the Research Council of Norway and
Department of Informatics, University of Bergen for their support. Csilla
Bujtás and Sandi Klavžar were supported by the Slovenian Research Agency
(ARRS) under the grants P1-0297, J1-2452, and N1-0285.

## Declaration of interests

The authors declare that they have no conflict of interest.

## Data availability

Our manuscript has no associated data.

## References

  * [1] S. Alikhani, N. Ghanbari, S. Soltani, Total dominator chromatic number of $k$-subdivision of graphs, Art Discrete Appl. Math. 6 (2023) paper 1.10.
  * [2] M. Arockiaraj, S. Klavžar, S. Mushtaq, K. Balasubramanian, Topological characterization of the full $k$-subdivision of a family of partial cubes and their applications to $\alpha$-types of novel graphyne and graphdiyne materials, Polycycl. Aromat. Comp. 41 (2021) 1902–1924.
  * [3] W. Barrett, S. Butler, M. Catral, S.M. Fallat, M. Shaun, H.T. Hall, L. Hogben, M. Young, The maximum nullity of a complete subdivision graph is equal to its zero forcing number, Electron. J. Linear Algebra 27 (2014) 444–457.
  * [4] A. Brandstädt, F. Mosca, Finding dominating induced matchings in $P_{9}$-free graphs in polynomial time, Discuss. Math. Graph Theory 42 (2022) 1139–1162.
  * [5] M. Dettlaff, M. Lemańska, J.A. Rodríguez-Velázquez, R. Zuazua, On the super domination number of lexicographic product graphs, Discrete Appl. Math. 263 (2019) 118–129.
  * [6] M.R. Garey, D.S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, WH Freeman and Co., New York, 1979.
  * [7] M.C. Golumbic, M. Lewenstein, New results on induced matchings, Discrete Appl. Math. 101 (2000) 157–165.
  * [8] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (Eds.), Topics in Domination in Graphs. Developments in Mathematics 64, Springer, Cham, 2020.
  * [9] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (Eds.), Structures of Domination in Graphs. Developments in Mathematics 66, Springer, Cham, 2021.
  * [10] R.M. Karp, Reducibility among combinatorial problems. In: Complexity of Computer Computations, R.E. Miller, J.W. Thatcher, J.D. Bohlinger eds., New York Plenum, 1972.
  * [11] S. Klavžar, K. Knauer, T. Marc, On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs, MATCH Commun. Math. Comput. Chem. 86 (2021) 327–342.
  * [12] D.J. Klein, J.A. Rodríguez-Velázquez, E. Yi, On the super domination number of graphs, Commun. Comb. Optim. 5 (2020) 83–96.
  * [13] B. Klemz, G. Rote, Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs, Algorithmica 84 (2022) 1064–1080.
  * [14] B. Krishnakumari, Y.B. Venkatakrishnan, Double domination and super domination in trees, Discrete Math. Algorithms Appl. 08 (2016) paper 1650067.
  * [15] D. Kobler, U. Rotics, Finding maximum induced matchings in subclasses of claw-free and P5-free graphs, and in graphs with matching and induced matching of equal maximum size, Algorithmica 37 (2003) 327–346.
  * [16] M. Lemańska, V. Swaminathan, Y.B. Venkatakrishnan, R. Zuazua, Super dominating sets in graphs, Proc. Nat. Acad. Sci. India Sect. A 85 (2015) 353–357.
  * [17] V. Lozin, I. Razgon, Tree-width dichotomy, European J. Combin. 103 (2022) paper 103517.
  * [18] V.D. Nguyen, B.T. Pham, P.T. Do, Efficient algorithms for maximum induced matching problem in permutation and trapezoid graphs, Fund. Inform. 182 (2021) 257–283.
  * [19] S. Saeedi Madani, D. Kiani, Induced matchings in strongly biconvex graphs and some algebraic applications, Math. Nachr. 294 (2021) 1160–1174.
  * [20] B. Senthilkumar, Y.B. Venkatakrishnan, H.N. Kumar, Super domination in trees, Discrete Math. Algorithms Appl. 14 (2022) paper 2150137.
  * [21] L.J. Stockmeyer, V.V. Vazirani NP-completeness of some generalizations of the maximum matching problem, Inf. Process. Lett. 15 (1982) 14–19.
  * [22] F. Wang, X. Liu, Coloring 3-power of 3-subdivision of subcubic graph, Discrete Math. Algorithms Appl. 10 (2018) paper 1850041.
  * [23] M. Xiao, H. Tan, Exact algorithms for maximum induced matching, Inform. and Comput. 256 (2017) 196–211.
  * [24] R. Yuster, U. Zwick, Finding even cycles even faster, SIAM J. Discrete Math. 10 (1997) 209–222.
  * [25] J. Zhou, L. Sun, C. Bu, Resistance characterizations of equiarboreal graphs, Discrete Math. 340 (2017) 2864–2870.
  * [26] W. Zhuang, Super domination in trees, Graphs Combin. 38 (2022) paper 21.