Extremal orders and races between palindromes in different bases

1.   Introduction

Throughout this paper, all graphs considered are finite, undirected, loopless and without multiple edges. We refer the reader to ^[3,18] for terminology and notation in graph theory.

Let $G = (V, E)$ be a graph of order $n$ with vertex set $V(G)$ and edge set $E(G)$. The open neighborhood of a vertex $v$ in $G$ is $N_G(v) = N(v) = \{u\in V(G)|uv\in E(G)\}$, and the closed neighborhood of $v$ is $N_G[v] = N[v] = N(v)\cup\{v\}$. The degree of a vertex $v$ in the graph $G$ is $d_G(v) = d(v) = |N(v)|$. Let $\delta(G) = \delta$ and $\Delta(G) = \Delta$ denote the minimum and maximum degree of a graph $G$, respectively. Denote by $G[H]$ the induced subgraph of $G$ induced by $H$ with $H\subset V(G)$. A vertex $v$ in $G$ is a $leaf$ if $d(v) = 1$. A vertex $u$ is a $support$ $vertex$ if $u$ has a leaf neighbor. Denote $L(u) = \{v|uv\in E(G), d(v) = 1\}$.

A subset $M\subseteq E(G)$ is called a matching in $G$ if no two elements are adjacent in $G$. A vertex $v$ is said to be $M$-saturated if some edges of $M$ are incident with $v$, otherwise, $v$ is $M$-unsaturated. If every vertex of $G$ is $M$-saturated, the matching $M$ is perfect. $M$ is a maximum matching if $G$ has no matching $M'$ with $|M'| > |M|$. Let $R$ be a subgraph of $G$, $M$ be a matching of $G$, $v\in V(R)$, $uv\in M$. We say the vertex $v$ is $R^I$ (resp. $R^O$) if $u\in V(R)$ (resp. $u\notin V(R)$).

A set $VC$ of vertices in a graph $G$ is a vertex cover of $G$ if all the edges are touched by the vertices in $VC$. A vertex cover $VC$ of $G$ is minimal if no proper subset of it is a vertex cover of $G$. A minimal vertex cover of maximum cardinality is called a $VC$-set. In 2001, Mishra et al. ^[13] denote by $MAX$-$MIN$-$VC$ the problem of finding a $VC$-set of $G$. Bazgan et al. ^[2] showed that $MAX$-$MIN$-$VC$ is APX-complete for cubic graphs.

A set $PD\subseteq V(G)$ in a graph $G$ is a paired dominating set if every vertex $v\notin PD$ is adjacent to a vertex in $PD$ and the subgraph induced by $PD$ contains a perfect matching. Paired domination was proposed in 1996 ^[9] and was studied for example in ^{[4,5,6,12,16,17]}. A paired dominating set $PD$ of $G$ is minimal if there is no proper subset $PD'\subset PD$ which is a paired dominating set of $G$. A minimal paired dominating set with maximum cardinality is called a $\Gamma_{pr}(G)$-set. The upper paired domination number of $G$ is the cardinality of a $\Gamma_{pr}(G)$-set of $G$. Denote by $Upper$-$PDS$ the problem of finding a $\Gamma_{pr}(G)$-set of $G$. Upper paired domination was introduced by Dorbec et al. in ^[7]. They investigated the relationship between the upper total domination and upper paired domination numbers of a graph. Later, they established bounds on upper paired domination number for connected claw-free graphs^[10]. Denote $Pr(v) = \{u|u\notin PD, N(u)\cap PD = \{v\}, uv\in E(G)\}$, where $PD$ is a minimal paired dominating set of $G$.

Recently, Michael et al. showed that $Upper$-$PDS$ is NP-hard for split graphs and bipartite graphs, and APX-completeness of $Upper$-$PDS$ for bipartite graphs with $\Delta = 4$ in ^[11]. In order to improve the results in ^[11], we show that $Upper$-$PDS$ is APX-complete for bipartite graphs with $\Delta = 3$.

2.   APX-completeness

The class APX is the set of NP-optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant.

First, we recall the notation of $L$-reduction ^[1,15]. Given two NP-optimization problems $H$ and $G$ and polynomial time transformation $f$ from instances of $H$ to instances of $G$, we say that $f$ is an $L$-reduction if there are positive constants $\alpha$ and $\beta$ such that for every instance $x$ of $H$:

(i) $opt_G(f(x))\leq \alpha opt_H(x)$;

(ii) for every feasible solution $y$ of $f(x)$ with objective value $m_G(f(x), y) = a$, we can find a solution $y'$ of $x$ with $m_H(x, y') = b$ in polynomial time such that $|opt_H(x)-b|\leq \beta|opt_G(f(x))-a|$.

To show that a problem $P\in APX$ is APX-complete, it's enough to show that there is an $L$-reduction from some APX-complete problems to $P$.

Denote by $MAX$-$MIN$-$VC$ the problem of finding a maximum minimal vertex cover of $G$. Note that, Minimum Domination problem is APX-complete even for bipartite graphs with maximum degree 3 ^[14], and Minimum Independent Domination problem ^[8] is the complement problem of $MAX$-$MIN$-$VC$ in a graph $G$. We can obtain an $L$-reduction from Minimum Domination problem to Minimum Independent Domination problem by replacing every edge $uv$ with a path $P_{uv} = uabcv$ with $\alpha = 7$, $\beta = 1$. It's clear that Minimum Independent Domination problem and $MAX$-$MIN$-$VC$ are in APX. Thus, Minimum Independent Domination problem is APX-complete even for bipartite graphs with maximum degree 3, so is $MAX$-$MIN$-$VC$ (by Theorem 7 in ^[2]).

In this section, we show $Upper$-$PDS$ for bipartite graphs with maximum degree 3 is APX-complete by providing an $L$-reduction $f$ from $MAX$-$MIN$-$VC$ for bipartite graphs with maximum degree 3.

We formalize the optimization problems as follows.

Lemma 1. ^[11] $Upper$-$PDS$ can be approximated with a factor of $2\Delta$ for graphs without isolated vertices and with maximum degree $\Delta$.

Therefore, $Upper$-$PDS$ is in APX.

Let $G = (V, E)$ be a bipartite graph with $|E| = m$, $\Delta(G) = 3$.

For each edge $xy\in E(G)$, let $H_{xy}$ be the graph which is shown in Figure 1. Let $T_1 = \{$ $a, ..., a_5,$ $b, ..., b_5,$ $r, ..., r_6,$ $s, ..., s_6,$ $c, .., c_3,$ $u, u_1, v, v_1\}$, $T_2 = \{p, ..., p_6,$ $q, ..., q_6,$ $d, ..., d_3, w, z\}$, $T_3 = \{h, .., h_5\}$, $T_4 = \{t, ..., t_5\}$, $V(H_{xy}) =$$V(T_1)\cup V(T_2)\cup V(T_3)\cup V(T_4)\cup \{w_1, z_1, x, y\}$, $|V(H_{xy})| = 70$.

Construct $G'$ by replacing each edge $xy\in E(G)$ with the graph $H_{xy}$.

It's clear, $\Delta(G') = 3$ and $G'$ is a bipartite graph.

Let $S_p = \{p, p_1, ..., p_6\}$, $S_q = \{q, q_1, ..., q_6\}$, $S_a = \{a, a_1, ..., a_5\}$, $S_b = \{b, b_1, ..., b_5\}$, $S_r = \{r, r_1, ..., r_6\}$, $S_s = \{s, s_1, ..., s_6\}$, $S_c = \{c, c_1, c_2, c_3\}$, $S_d = \{d, d_1, d_2, d_3\}$.

Let $xy = e\in E(G)$, $H_{e}' = H_{xy}' = H_{xy}-\{x, y\}$, $|V(H_{xy}')| = 68$.

Let $PD$ be a paired dominating set of $G'$, $uv\in E(G)$. We say $H_{uv}'$ is $[I, O]$ if $u$ is $H_{uv}^I$ and $v$ is $H_{uv}^O$, or if $v$ is $H_{uv}^I$ and $u$ is $H_{uv}^O$. We say $H_{uv}'$ is $[I, 0]$ if $u$ is $H_{uv}^I$ and $v\notin PD$, or if $u\notin PD$ and $v$ is $H_{uv}^I$. Analogously, $H_{uv}'$ could be $[0, 0]$ ($[I, I]$ or $[O, O]$ or $[O, 0]$).

Note that

The following lemma is immediate.

Lemma 2. Let $PD$ be a minimal paired dominating set of $G$, $M$ be a perfect matching of $G[PD]$. If $v, u$ are support vertices, $uv\in E(G)$, $x\in L(v)$, $y\in L(u)$, then $|\{x, y\}\cap PD|\leq 1$.

Lemma 3. Let $PD$ be a minimal paired dominating set of $G'$, $M$ be a perfect matching of $G'[PD]$. For each $H_{xy}$, we have

(a) $|S_c\cap PD| = 4$ if and only if $r, s\notin PD$, $Pr(c_3)\neq \emptyset$ or $Pr(c)\neq \emptyset$.

(b) $|S_d\cap PD| = 4$ if and only if $p, q \notin PD$, $Pr(d_3)\neq \emptyset$ or $Pr(d)\neq \emptyset$.

(c) $|T_3\cap PD|\leq 4$ with equality if and only if (i) or (ii) holds,

(i) $Pr(h_1)\neq \emptyset$ if $h\notin PD$,

(ii) $N(h)\cap PD = \{h_1\}$ or $Pr(h)\neq \emptyset$ if $h\in PD$.

And if $h$ is $G[T_3]^O$, $|T_3\cap PD| = 3$.

(d) $|T_4\cap PD|\leq 4$ with equality if and only if (i) or (ii) holds,

(i) $Pr(t_1)\neq \emptyset$ if $t\notin PD$,

(ii) $N(t)\cap PD = \{t_1\}$ or $Pr(t)\neq \emptyset$ if $t\in PD$.

And if $t$ is $G[T_4]^O$, $|T_4\cap PD| = 3$.

(e) $|S_a\cap PD|\leq 4$ with equality if and only if (i) or (ii) holds,

(i) $Pr(a_1)\neq \emptyset$ if $a\notin PD$,

(ii) $N(a)\cap PD = \{a_1\}$ or $Pr(a)\neq \emptyset$ if $a\in PD$.

And if $a$ is $G[S_a]^O$, $|S_a\cap PD| = 3$.

(f) $|S_b\cap PD|\leq 4$ with equality if and only if (i) or (ii) holds,

(i) $Pr(b_1)\neq \emptyset$ if $b\notin PD$,

(ii) $N(b)\cap PD = \{b_1\}$ or $Pr(b)\neq \emptyset$ if $b\in PD$.

And if $b$ is $G[S_b]^O$, $|S_b\cap PD| = 3$.

(g) $3\leq |S_r\cap PD|\leq 4$. And if $r\in PD$ and $r$ is $G[S_r]^O$, $|S_r\cap PD| = 3$.

(h) $3\leq |S_s\cap PD|\leq 4$. And if $s\in PD$ and $s$ is $G[S_r]^O$, $|S_s\cap PD| = 3$.

(i) $3\leq |S_p\cap PD|\leq 4$. And if $p\in PD$ and $p$ is $G[S_p]^O$, $|S_p\cap PD| = 3$.

(j) $3\leq |S_q\cap PD|\leq 4$. And if $q\in PD$ and $q$ is $G[S_q]^O$, $|S_q\cap PD| = 3$.

(k) $|T_2\cap PD|\leq 13$ with equality if and only if $|\{w, z\}\cap PD| = 1$.

(l) $|T_1\cap PD|\leq 22$ with equality if and only if $\{u, v\}\subseteq PD$.

(m) If $\{u, v\}\cap PD = \emptyset$, $|T_1\cap PD|\leq 18$.

Proof. (a) W.l.o.g. we consider $r\in PD$. If $rc\in M$, $|S_c\cap PD|\neq 4$. Otherwise, $c_1c_2, c_3s\in M$ and let $PD' = PD\setminus\{c_1, c_2\}$, $M' = M\setminus\{c_1c_2\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction. If $rc\notin M$, $|S_c\cap PD|\neq 4$. Otherwise, $cc_1, c_2c_3\in M$ and let $PD' = PD\setminus\{c, c_1\}$, $M' = M\setminus\{cc_1\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

If $Pr(c_3) = \emptyset$ and $Pr(c) = \emptyset$, let $PD' = PD\setminus\{c, c_3\}$ and $M' = M\setminus\{cc_1, c_2c_3\}\cup \{c_1c_2\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

(b) The proof is analogous to that of (a), and the proof is omitted.

(c) Clearly, $|T_3\cap PD|\leq 4$. If $|T_3\cap PD| = 4$, $\{h_1, h_2, h_3, h_4\}\subseteq PD$ or $\{h, h_1, h_2, h_3\}\subseteq PD$. If $\{h_1, h_2, h_3, h_4\}\subseteq PD$, $Pr(h_1)\neq\emptyset$. Otherwise, let $PD' = PD\setminus\{h_4, h_1\}$, $M' = M\setminus\{h_3h_4, h_1h_2\}\cup \{h_2h_3\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction. If $\{h, h_1, h_2, h_3\}\subseteq PD$, $N(h)\cap PD = \{h_1\}$ or $Pr(h)\neq \emptyset$. Otherwise, let $PD' = PD\setminus\{h, h_1\}$, $M' = M\setminus\{hh_1\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

If $h$ is $G[T_3]^O$, and since $|T_3\setminus\{h\}\cap PD|$ is even, we have $|T_3\cap PD| = 3$.

(d)–(f) We obtain the conclusions with a similar proof of (c).

(g) Clearly, $3\leq |S_r\cap PD|\neq 6$. If $|S_r\cap PD| = 5$, we obtain $S_r\cap PD = \{r, r_1, r_2, r_3, r_4\}$ or $S_r\cap PD = \{r, r_2, r_3, r_4, r_5\}$ by Lemma 2. Therefore, $PD$ is not a minimal paired dominating set, a contradiction. Thus, $3\leq |S_r\cap PD|\leq 4$.

If $r$ is $G[S_r]^O$, and since $|S_r\setminus\{r\}\cap PD|$ is even, we have $|S_r\cap PD| = 3$.

(k) Since $|S_d\cap PD|\leq 4$, $|T_2\cap PD|\leq 14$ by (i)–(j) and Eq (2.1).

If $|\{w, z\}\cap PD| = 0$, $|T_2\cap PD|\leq 12$.

If $|\{w, z\}\cap PD| = 1$, $|T_2\cap PD|\leq 13$.

Then we consider $|\{w, z\}\cap PD| = 2$. If $w$ is $G[T_2]^I$ or $z$ is $G[T_2]^I$, we may assume $w$ is $G[T_2]^I$. We obtain $wp\in M$, $|S_p\cap PD| = 3$ by (i), $|S_d\cap PD|\leq 3$ by (b). Therefore, $|T_2\cap PD|\leq 12$ by Eq (2.1). If $w, z$ are $G[T_2]^O$, $|S_d\cap PD|\leq 3$ by (b). Since $|T_2\cap PD|$ is even, $|T_2\cap PD|\leq 12$ by Eq (2.1).

Thus, $|T_2\cap PD|\leq 13$ with equality if and only if $|\{w, z\}\cap PD| = 1$, see Figure 2 (a).

(h)–(j) Using similar arguments of (g), the conclusions follow.

(l)–(m) We discuss the following cases.

Case 1. $|\{u, v\}\cap PD| = 2$.

In this case, we have $|\{u_1, v_1\}\cap PD|\geq 1$, $|S_a\cap PD|\geq 3$ and $|S_c\cap PD|\geq 3$, otherwise, $|T_1\cap PD|\leq 22$ by (e)–(h) and Eq (2.2).

W.l.o.g. we assume $u_1\in PD$.

First, we assume that $|S_a\cap PD| = 4$. We obtain $aa_1, uu_1\in M$, $\{r, c, r_1\}\cap PD = \emptyset$ by (e). Thus, $|S_c\cap PD|\leq 3$. Then, we consider $|S_c\cap PD| = 3$, that is, $c_3s\in M$. By (h), we have $|S_s\cap PD| = 3$. Therefore, $|T_1\cap PD|\leq 22$ by Eq (2.2).

Then, we consider $|S_a\cap PD| = 3$. Therefore, $v_1\in PD$, otherwise, $|T_1\cap PD|\leq 22$ by Eq (2.2).

We have $|S_b\cap PD| = 4$, otherwise, $|T_1\cap PD|\leq 22$ by Eq (2.2). By (f), $\{s, s_1, c_3\}\cap PD = \emptyset$. Thus, $|S_c\cap PD|\leq 3$. Therefore, $|T_1\cap PD|\leq 22$ by Eq (2.2), see Figure 2 (b).

Case 2. $|\{u, v\}\cap PD| = 1$.

W.l.o.g. we assume $u\in PD$.

We have $|\{u_1, v_1\}\cap PD|\geq 1$ and $|S_a\cap PD|\geq 3$, otherwise, $|T_1\cap PD|\leq 21$ by Eq (2.2).

Case 2.1 $u_1\in PD$.

If $|S_a\cap PD| = 4$, $\{r, r_1, c\}\cap PD = \emptyset$ by (e). Then $|S_c\cap PD|\leq 3$. If $|S_c\cap PD| = 3$, we have $c_3s\in M$, $|S_s\cap PD|\leq 3$ by (h). Therefore, $|T_1\cap PD|\leq 21$ by Eq (2.2). If $|S_c\cap PD| = 2$, $|T_1\cap PD|\leq 21$ by Eq (2.2).

Now we consider $|S_a\cap PD| = 3$. If $v_1\notin PD$, $|T_1\cap PD|\leq 21$ by Eq (2.2). Thus, $v_1\in PD$, that is, $v_1b\in M$. Therefore, $|S_b\cap PD| = 3$ by (f), $|T_1\cap PD|\leq 21$ by Eq (2.2).

Case 2.2 $u_1\notin PD$.

If $v_1\in PD$, $v_1b\in M$. Therefore, $|S_b\cap PD| = 3$ by (f), $|T_1\cap PD|\leq 21$ by Eq (2.2). Thus, $v_1\notin PD$, and $|T_1\cap PD|\leq 21$ by Eq (2.2).

Case 3. $|\{u, v\}\cap PD| = 0$.

In this case, $|T_1\cap PD|$ is even.

Case 3.1 $|\{u_1, v_1\}\cap PD|\geq 1$.

W.l.o.g. we assume $u_1\in PD$. Then $u_1a\in M$, $|S_a\cap PD| = 3$ by (e). If $v_1\notin PD$, $b\in PD$. By (a), $|S_c\cap PD|\leq 3$. Therefore, $|T_1\cap PD|\leq 19$ by Eq (2.2). If $v_1\in PD$, we obtain $v_1b\in M$, $|S_b\cap PD| = 3$ by (f). $|S_c\cap PD|\leq 3$ by (a). Therefore, $|T_1\cap PD|\leq 19$ by Eq (2.2).

Case 3.2 $|\{u_1, v_1\}\cap PD| = 0$.

In this case, $a, b\in PD$. By (a), $|S_c\cap PD|\leq 3$. Therefore, $|T_1\cap PD|\leq 19$ by Eq (2.2).

Note that $|T_1\cap PD|$ is even, so $|T_1\cap PD|\leq 18$, see Figure 2 (c).

Thus, (l) and (m) hold.

Lemma 4. Let $PD$ be a minimal paired dominating set of $G'$.

(a) $|V(H'_{xy})\cap PD|\leq 43$.

(b) If $\{xw_1, yz_1\} \subset M$, $|V(H'_{xy})\cap PD|\leq 42$.

(c) If $\{xw_1, yz_1\} \cap M = \emptyset$ and $\{w_1, z_1\}\subseteq PD$, $|V(H'_{xy})\cap PD|\leq 42$.

(d) If $xw_1 \notin M(G)$, $w_1\in PD$ and $y\notin PD$, then $|V(H'_{xy})\cap PD|\leq 42$.

Proof. (a) By Lemma 3 and Eq (2.3),

We consider that $\{w_1, z_1\}\cap PD\neq \emptyset$, $|T_4\cap PD|\geq3$ and $|T_3\cap PD|\geq3$, otherwise, $|V(H'_{xy})\cap PD|\leq 43$. Then, w.l.o.g. we assume that $w_1\in PD$.

If $|T_4\cap PD| = 4$, $\{tt_1, t_2t_3\}\subseteq M$ or $\{t_1t_2, t_3t_4\}\subseteq M$.

If $\{tt_1, t_2t_3\}\subseteq M$, $Pr(t)\neq \emptyset$ or $N(t)\cap PD = \{t_1\}$. If $Pr(t)\neq \emptyset$, $u\in Pr(t)$. By Lemma 3 (m), $|V(H'_{xy})\cap PD|\leq 43$. If $N(t)\cap PD = \{t_1\}$, we have $u, w_1\notin PD$, $|T_1\cap PD|\leq 21$ by Lemma 3 (l). Then we obtain $z\in PD$, otherwise, $|V(H'_{xy})\cap PD|\leq 43$ by Lemma 3 (k) and Eq (2.3). If $|T_3\cap PD| = 4$, we have $v\notin PD$, therefore, $|V(H'_{xy})\cap PD|\leq 43$ by Eq (2.3). If $|T_3\cap PD| = 3$, $|V(H'_{xy})\cap PD|\leq 43$ by Eq (2.3).

If $\{t_1t_2, t_3t_4\}\subseteq M$, $\{w, u\}\cap PD = \emptyset$. By Lemma 3 (l), $|T_1\cap PD|\leq 21$, and $v\in PD$. If $z\notin PD$, $|V(H'_{xy})\cap PD|\leq 43$ by Lemma 3 (k) and Eq (2.3). If $z\in PD$, $|T_3\cap PD|\leq 3$ by Lemma 3 (c). Therefore, $|V(H'_{xy})\cap PD|\leq 43$ by Eq (2.3).

If $|T_4\cap PD| = 3$, we consider $|T_1\cap PD| = 22$, and $\{u, v, z_1\}\in PD$. We have $|T_3\cap PD|\neq 4$ by Lemma 3 (c). Therefore, $|V(H'_{xy})\cap PD|\leq 43$ by Eq (2.3).

(b)–(d) Since $|V(H'_{xy})\cap PD|\leq 43$, and, $|V(H'_{xy})\cap PD|$ is even in those cases, so $|V(H'_{xy})\cap PD|\leq 42$.

Lemma 5. Let $PD$ be a minimal paired dominating set of $G'$, $M$ be a perfect matching of $G'[PD]$.

(a) If $\{x, w_1, y, z_1\}\subset PD$, $xw_1\in M(G)$ and $yz_1\notin M$, we have $|V(H'_{xy})\cap PD|\leq 41$.

(b) If $\{x, y\}\cap PD = \emptyset$, $|V(H'_{xy})\cap PD|\leq 40$.

Proof. (a) In this case, we have $z\in PD$ and $zz_1\in M$.

Since $|V(H'_{xy})\cap PD|$ is odd, it's sufficient to show $|V(H'_{xy})\cap PD|\leq 42$. We only consider $\{u, v\}\cap PD\neq \emptyset$ by Lemma 3 (m).

Case 1. $|T_4\cap PD| = 4$.

In this case, we have $\{t_1t_2, t_3t_4\}\subseteq M$ or $\{tt_1, t_2t_3\}\subseteq M$. If $\{t_1t_2, t_3t_4\}\subseteq M$ (or $\{tt_1, t_2t_3\}\subseteq M$), we obtain $u, w \notin PD$, $v\in PD$. Since $z, v\in PD$, $|T_3\cap PD|\leq 3$ by Lemma 3 (c). If $|T_3\cap PD| = 2$, $|V(H'_{xy})\cap PD|\leq 42$ by Eq (2.3). If $|T_3\cap PD| = 3$, $hv\in M$. Thus, $\{q, q_1, d_3\}\cap PD = \emptyset$, otherwise, let $PD' = PD\setminus\{z, z_1\}$, $M' = M\setminus\{zz_1\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction. Since $zz_1\in M$, we obtain that $|T_2\cap PD|$ is odd. So $|T_1\cap PD|\leq 12$. Therefore, $|V(H'_{xy})\cap PD|\leq 42$ by Eq (2.3), see Figure 3 (a).

Case 2. $|T_4\cap PD| = 3$.

If $tw\in M$, $u\notin PD$ or $\{p, p_1, d\}\cap PD = \emptyset$. Otherwise, let $PD' = PD\setminus\{t, w\}$, $M' = M\setminus\{tw\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction. If $\{p, p_1, d\}\cap PD = \emptyset$, $|S_d\cap PD|\leq 3$. W have $|S_d\cap PD| = 3$, $d_3q\in M$, otherwise, $|V(H'_{xy})\cap PD|\leq 42$ by Eq (2.3). Thus $|S_q\cap PD|\leq 3$ by Lemma 3 (j) and Eq (2.3), and $|V(H'_{xy})\cap PD|\leq 42$. If $u\notin PD$, $v\in PD$. Thus, $|T_3\cap PD|\leq 3$ by Lemma 3 (c) and Eq (2.3), and $|V(H'_{xy})\cap PD|\leq 42$.

If $tu\in M$, $|T_3\cap PD|\leq 3$ by Lemma 3 (c). We have $|T_3\cap PD| = 3$, $hv\in M$, otherwise, $|V(H'_{xy})\cap PD|\leq 42$ by Eq (2.3). Let $PD' = PD\setminus\{t, h\}$, $M' = M\setminus\{tu, hv\}\cup \{uv\}$. Therefore, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

Case 3. $|T_4\cap PD| = 2$.

Now we only consider $|T_1\cap PD| = 22$, and $\{u, v\}\subset PD$. By Lemma 3 (c) and Eq (2.3), $|V(H'_{xy})\cap PD|\leq 42$.

(b) Since $|V(H'_{xy})\cap PD|$ is even, it's sufficient to show $|V(H'_{xy})\cap PD|\leq 41$.

Case 1. $|\{z_1, w_1\}\cap PD| = 0$.

We obtain $\{z, w\}\subseteq PD$, $|T_2\cap PD|\leq 12$ by Lemma 3 (k). If $|T_4\cap PD|\leq 3$, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3), see Figure 3 (b). If $|T_4\cap PD| = 4$, $t\in PD$ and $Pr(t)\neq \emptyset$ by Lemma 3(d). So, $\{u, v, u_1\}\cap PD = \emptyset$. By Lemma 3 (m) and Eq (2.3), $|V(H'_{xy})\cap PD|\leq 40$.

Case 2. $|\{z_1, w_1\}\cap PD| = 1$.

W.l.o.g. we assume $w_1\in PD$. Thus, $ww_1\in M$, $z\in PD$, $|T_2\cap PD|\leq 12$ by Lemma 3 (k). If $|T_4\cap PD| = 2$, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3). If $|T_4\cap PD| = 4$, we obtain $Pr(t) = \{u\}$ for $t\in PD$, $\{u, u_1, v\}\cap PD = \emptyset$. By Lemma 3 (m) and Eq (2.3), $|V(H'_{xy})\cap PD|\leq 40$. If $|T_4\cap PD| = 3$, $tu\in M$. And $v\in PD$, otherwise $|T_1\cap PD|\leq 21$ by Lemma 3 (l), $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3). Thus, $|T_4\cap PD|\neq 4$ by Lemma 3 (d). Afterwards, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3).

Case 3. $|\{z_1, w_1\}\cap PD| = 2$.

Thus, $ww_1\in M$, $zz_1\in M$, $|T_2\cap PD|\leq 12$ by Lemma 3 (k).

If $|T_4\cap PD| = 4$, $t\in PD$ and $\{u, u_1, v\}\cap PD = \emptyset$. By Lemma 3 (m) and Eq (2.3), we have $|V(H'_{xy})\cap PD|\leq 40$.

If $|T_4\cap PD| = 3$, we have $tu\in M$, and $|T_3\cap PD|\leq 3$ by Lemma 3 (c). If $|T_3\cap PD| = 2$, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3). If $|T_3\cap PD| = 3$, $hv \in M$. Let $PD' = PD\setminus\{t, h\}$, $M' = M\setminus\{tu, hv\}\cup \{uv\}$. Therefore, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

If $|T_4\cap PD| = 2$, we only consider $|T_1\cap PD| = 22$. Thus, $u, v\in PD$. By Lemma 3 (c), $|T_3\cap PD|\leq 3$. Therefore, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3).

Corollary 6. Let $PD$ be a minimal paired dominating set of $G'$. If $|V(H_{uv}')\cap PD| = 43$ if and only if $|\{u, v\}\cap PD| = 1$, and, $u$ or $v$ is $H_{uv}^I$.

Lemma 7. If $VC_1$ is a minimal vertex cover of $G$, there exists a minimal paired dominating set $PD_1$ of $G'$ with $|PD_1| = 42m+2|VC|$.

Proof. A minimal paired dominating set $PD_1$ can be constructed by the following manner:

For each vertex $x\in VC_1$, we have $|N(x)\cap VC_1| < d(x)\leq3$. So there exists at least one edge $xx_1$ with $x_1\notin VC_1$ in $G$, and maybe exist edges $xx_2$ or $xx_3$.

Therefore, for the edge $xx_1$, put $i$ into $PD'$ for $i\in \{x, w_1,$ $p_2, p_3, p_4, p_5,$ $d, d_1, d_2, d_3,$ $q_2, q_3, q_4, q_5,$ $z, z_1,$ $h, h_2, h_3,$ $v,$ $b_1, b_2, b_3, b_4,$ $s_2, s_3, s_4, s_5,$ $c, c_1, c_2, c_3,$ $r_2, r_3, r_4, r_5,$ $a, a_1, a_2, a_3,$ $t_1, t_2, t_3, t_4\}.$ Put $j$ into $M$ for $j\in\{xw_1,$ $p_5p_4, p_3p_2, dd_1, d_2d_3,$ $q_2q_3, q_4q_5,$ $zz_1,$ $hv,$ $h_2h_3,$ $b_1b_2, b_3b_4,$ $s_2s_3, s_4s_5,$ $cc_1, c_2c_3,$ $r_2r_3, r_4r_5,$ $aa_1, a_2a_3,$ $t_1t_2, t_3t_4\}.$ See Figure 4 (a).

For edges $xx_2, xx_3$, put $i$ into $PD'$ for $i\in \{x,$ $p_2, p_3, p_4, p_5,$ $d, d_1, d_2, d_3,$ $q_2, q_3, q_4, q_5,$ $z, z_1,$ $u, v,$ $h_2, h_3,$ $b_1, b_2, b_3, b_4,$ $s_2, s_3, s_4, s_5,$ $c, c_1, c_2, c_3,$ $r_2, r_3, r_4, r_5,$ $a_1, a_2, a_3, a_4,$ $t_1, t_2, t_3, t_4\}.$ Put $j$ into $M$ for $j\in\{$ $p_5p_4, p_3p_2, dd_1, d_2d_3,$ $q_2q_3, q_4q_5,$ $zz_1,$ $h_2h_3,$ $uv,$ $b_1b_2, b_3b_4,$ $s_2s_3, s_4s_5,$ $cc_1, c_2c_3,$ $r_2r_3, r_4r_5,$ $a_1a_2, a_3a_4,$ $tt_1, t_2t_3\}.$ See Figure 4 (b).

Let $PD_1 = PD'\cup VC_1$. Since vertex $x$ is $M$-saturated in $PD_1$. Therefore, $PD_1$ is a paired dominating set of $G'$.

Since $N(w)\cap PD_1 = \{w_1\}$, then $PD_1\setminus\{w_1\}$ is not a dominating set of $G'$. So $PD_1$ is a minimal paired dominating set of $G'$. And $|PD_1| = |VC_1|+ |VC_1|\times 43 + (m-|VC_1|)\times 42$. Therefore, $|PD_1| = 2|VC_1|+ 42m.$

Let $PD$ be a minimal paired dominating set of $G'$. Algorithm 1 is to obtain a minimal vertex cover $VC$ of $G$, and it terminates in polynomial time.

Lemma 8. If $PD$ is a minimal paired dominating set of $G'$ and $VC$ is a minimal vertex cover of $G$ obtained by Algorithm 1, $|VC|\geq |PD|-42m- |VC|$.

Proof. Let $M$ be the perfect matching of $G[PD]$, $m_e = V(H_{xy}')\cap PD$ where $e = xy\in E(G)$, $M_e = \bigcup_{e\in E(G)}m_e$, $Le = V(G)\setminus (Mo\cup In \cup De)$.

In Algorithm 1, we have:

Claim 9. (a) If $v$ is put into $Mo$ by the while loop (lines 11 to 13) or $De$ (line 18), $v$ will not be put into $In$ later.

(b) For every vertex $v\in V(G)$, $v$ will be put into $Mo$ (or $De$ or $In$) at most once.

(c) $Mo\cap De = \emptyset$, $Mo\cap In = \emptyset$.

(d) If $v\in De$, there exists a vertex $w\in N(v)\cap In$.

(e) If vertex $v\in De\cap In$, we have $v\notin VC'$, that is, $v$ is put into $In$ at first and then into $De$.

(f) If $u, v\in De\cup Mo$, $N(v)\cap N(u)\cap Mo \cap De = \emptyset$.

(g) If $v\in De\setminus In$, there exists a vertex $u\in N(v)\cap (In\setminus De)$, $u\notin VC'$. And $|N(u)\cap De|\leq 2$. What's more, there exists a vertex $w\in N(u) \setminus VC'$. If $w\in In\setminus De$, $|(N(u)\cup N(w))\cap (De\setminus In) |\leq 3$.

Proof. (a) After $v$ is put into $De$ (or $Mo$), every $w\in N(v)$ has a neighbor $v$ which does not belong to $VC$, so $w$ will not be put into $De$. Therefore, $v$ will not be put into $In$ later.

(b)–(d) By (a), it is immediate.

(e) By (a) and (c), it is immediate.

(f) Suppose $v$ is put into $De\cup Mo$. By (a), $w\in N(v)$ will not be put into $De\cup Mo$.

(g) For vertex $v\in De\setminus In$, by (d) and (f), let $u\in N(v)\cap (In\setminus De)$, and $u\notin VC'$, $|N(u)\cap De|\leq 2$.

Since $u\in In\setminus De$, there exists a vertex $w\in N(u) \setminus VC'$.

Since $1\leq |N(u)\cap (De\setminus In) |\leq 2$, $|N(w)\cap (De\setminus In) |\leq 2$. If $w\in In\setminus De$, we may assume $u$ is put into $In$ at first. Then $N(u)\cap (De\setminus In) |\leq 1$, otherwise, $w$ will not be put into $In$ later. Therefore, $|(N(u)\cup N(w))\cap (De\setminus In) |\leq 3$.

Thus,

To show that $|M_e|+|Mo|+|De|-|In| \leq 42m+|VC|$, we use the following strategy.

Discharging procedure:

In the graph $G'$, we set the initial charge of every vertex $v$ to be $s(v) = 1$ for $v\in Mo \cup M_e\cup (De\setminus In)$, $s(v) = -1$ for $v\in In \setminus De$, $s(v) = 0$ otherwise, $s(H_{uv}') = \sum_{x\in V(H_{uv}')}s(x)$, $s(G') = \sum_{v\in V(G')}s(v)$.

Obviously,

We use the discharging procedure, leading to a final charge $s'$, defined by applying the following rules:

Rule 1: For the vertex $v\in Mo$, $v$ is $M$-saturated. Therefore, $v$ is $H_{uv}^I$ for $u$. If $u$ is $H_{uv}^I$, $s(v)$ transmits 1 charge to $s(u)$. If $u$ is $H_{uv}^O$, $s(v)$ transmits 1 charge to $s(H_{uv}')$ which is $[I, O]$.

Rule 2: For each $s(H_{uv}') = 43$, by Corollary 6, $s(H_{uv}')$ transmits 1 charge to $u\in VC'$.

Rule 3: For the vertex $v\in De\setminus In$, by Claim 9 (g), there exists a vertex $u\in N(v)\cap (In\setminus De)$, and a vertex $w\in N(u) \setminus VC'$ and $|N(u)\cap De|\leq 2$. If $|N(u)\cap De| = 2$, $s(v)$ transmits 1 charge to $s(u)$ and transmits 1 charge to $s(H_{uw}')$ which is $[0, 0]$. If $|N(u)\cap De| = 1$, $s(v)$ transmits 2 charge to $s(u)$.

After discharging, we have:

Claim 10. (a) $s'(v)\leq 0$ for $v\in Mo\cup (De \setminus In) \cup (Le\setminus VC) \cup (In\cap De)$.

(b) For each $H_{xy}'$, $s'(H_{xy}')\leq 42$.

(c) $s'(v)\leq 1$ for $v\in (In \setminus De)\cup (Le\cap VC)$.

Proof. (a) If $v\in Mo$, by Claim 9 (f), $v$ will not receive any charge by Rules 1 and 3. Since $N[v]\cap VC' = N[v]$. By Lemmas 4 and 5, $v$ will not receive any charge by Rule 2. Therefore, $s'(v) = 0$.

If $v\in De \setminus In$, $v\in VC'$. By Claim 9 (f), $N(v)\cap Mo = \emptyset$. Thus, $v$ will not receive any charge by Rules 1 and 3. Since $v$ is $H_{uv}^I$ for $u$. By Lemmas 4 and 5, if $u\in VC'$, $v$ will not receive any charge by Rule 2. If $u\notin VC'$, $v$ will receive 1 charge at most by Rule 2. Afterwards, by Rule 3, $v$ will transmit 2 charge to others, so $s'(v)\leq 0$.

If $v\in Le\setminus VC$, $v$ will not receive any charge by Rules 1, 2 and 3.

If $v\in In\cap De$, $v\notin VC'$ by Claim 9 (e). Thus, $v$ will not receive any charge by Rules 1 and 2. By Claim 9 (f), $v\in De$, $N(v)\cap De = \emptyset$. Thus, $v$ will not receive any charge by Rule 3.

(b) If $H_{uw}'$ is $[I, I]$ or $[O, O]$ or $[I, 0]$ or $[O, 0]$, $s(H_{uw}')$ will not receive any charge by Rules 1, 2 and 3. If $H_{uw}'$ is $[0, 0]$, $s(H_{uw}')$ will not receive any charge by Rules 1 and 2.

If $H_{uw}'$ is $[0, 0]$, by Claim 9 (g), $|(N(u)\cup N(w))\cap (De\setminus In) |\leq 3$. Thus, $s(H_{uw}')$ will receive 2 charge at most from $s(x)$ where $x\in N(v)\setminus \{w\}$ by Rule 3.

And if $s(H_{uw}') = 43$, by Corollary 6, there exists a vertex $u\in VC'$ and $u$ is $H_{uw}^I$. Therefore, $s'(H_{uw}') = 42$ by Rule 2.

Thus, by Lemmas 4 and 5, $s'(H_{uw}')\leq 42$.

(c) If $v\in In\setminus De$, $v\notin VC'$, $v$ will receive any charge by Rules 1 and 2. And there exists a vertex $w\in N(v)$ $w\notin VC'$ and $w\notin De\setminus In$. So $v$ will receive 2 charge at most by Rule 3, $s'(v)\leq -1+2 = 1$.

If $v\in Le\cap VC$, $v$ will receive any charge by Rule 3. By Lemmas 4, 5 and Corollary 6, $H_{uv}'$ is $[I, 0]$ if $s(H_{uv}') = 43$. Since $v$ can be $M$-saturated once, $v$ will receive 1 charge at most by Rules 1 and 2. Thus, $s'(v)\leq 0+1 = 1$.

By Claim 10,

Thus, by Eq (2.4),

Let $PD^*$ be a $\Gamma_{pr}(G')$-set of $G'$, and be the Input of Algorithm 1. Then we obtain the Output $VC$ by Algorithm 1.

Since

By Lemma 8,

Let $VC^*$ be a $VC$-set of $G$. Since $|VC|\leq |VC^*|$,

By Lemma 7, $|PD^*|\geq |PD_1| = 42m+2|VC^*|$. By Lemma 8,

Thus,

Therefore, by Eq (2.6) and Eq (2.7), $f$ is an $L$-reduction with $\alpha = 128$, $\beta = 1$.

3.   Conclusions

$Upper$-$PDS$ for bipartite graphs is proved to be APX-complete with maximum degree 4 and still open with maximum degree 3. In this paper, we show that $Upper$-$PDS$ for bipartite graphs with maximum degree 3 is APX-complete by providing an $L$-reduction $f$ from $MAX$-$MIN$-$VC$ for bipartite graphs to it.

Acknowledgments

This work was supported by the National Key R & D Program of China (No. 2018YFB1005100), the Guangzhou Academician and Expert Workstation (No. 20200115-9) and the Innovation Ability Training Program for Doctoral student of Guangzhou University (No. 2019GDJC-D01).

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.