A proof of a conjecture on the paired-domination subdivision number

Abstract

A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. It was conjectured that the paired-domination subdivision number is at most $n-1$ for every connected graph G of order $n\ge 3$ which does not contain isolated vertices. In this paper, we settle the conjecture in the affirmative.

1 Introduction

Throughout the paper, G is a simple connected graph with vertex set V(G) and edge set E(G) (briefly V and E). Let $\left| V(G)\right| =n$ denote the order of G. For every vertex $v\in V(G)$, the open neighborhood of v is the set $N_{G}(v)=\{{u\in V(G)|uv\in E(G)\}}$ and the closed neighborhood of v is the set $N_{G}[v]=N_{G}(v)\cup \{v\}$. The degree of a vertex v is $\deg _{G}(v)=|N_{G}(v)|$. When no confusion arises, we will delete the subscript G in $N_{G}$ and $\deg _{G}.$ A vertex of degree one is called a leaf and its neighbor is called a support vertex. A support vertex is said to be strong if it is adjacent to at least two leaves. We call the core of a graph G, denoted by C(G),  the set of vertices of G which are neither leaves nor support vertices. For any two vertices u and v in G, the distance d(u, v) equals the length (number of edges) of a shortest path between u and v in G. For any integer $k\ge 0$, let $N_{k}(v)$ denote the set of vertices of G that are at distance k from v. Clearly, $N_{0}(v)=\{v\}$ and $N_{1}(v)=N(v)$. The eccentricity ecc(v) of a vertex v in a connected graph G is the distance between v and a vertex furthest from v. A matching in a graph G is a set of pairwise non-intersecting edges, while a perfect matching in G is a matching that covers each vertex.

A dominating set of G is a subset S of V such that every vertex in $V-S$ has at least one neighbor in S. A subset S of V is a paired-dominating set of G,  abbreviated PDS, if S is a dominating set and the subgraph induced by the vertices of S contains a perfect matching. The paired-domination number $\gamma _{pr}(G)$ is the minimum cardinality of a PDS of G. If S is a paired-dominating set with a perfect matching M, then two vertices u and v are said to be partners (or paired) in S if the edge $uv\in M$. We call a PDS of minimum cardinality a $\gamma _{pr}(G)$-set. Note that every graph G without isolated vertices has a PDS since the endvertices of any maximal matching in G form such a set. Paired-domination was introduced by Haynes and Slater [9] and is studied, for example, in [2, 3, 5, 8, 10,11,12].

The main focus of our paper is the study of the paired-domination subdivision number introduced by Favaron et al. in [6] and defined as follows. The paired-domination subdivision number $\mathrm {sd}_{\gamma _{pr}}(G)$ of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the paired-domination number of G. Observe that since the paired-domination subdivision number of the graph $K_{2}$ remains unchanged when its only edge is subdivided, we will assume in our study that the graph G has order at least 3. The paired-domination subdivision number has been studied by several authors [1, 4, 7, 13, 14].

Favaron et al. [6] posed the following conjecture.

Conjecture 1

([6]) For every connected graph G of order $n\ge 3$, $\mathrm {sd}_{{\gamma }_{pr}}(G)\le n-1.$

In connection with Conjecture 1, Egawa et al. [4] proved that for every connected graph G of order $n\ge 4,$ $\mathrm {sd}_{\gamma _{pr}}(G)\le 2n-5.$ Moreover, if further G has an edge uv such that u and v are not partners in any $\gamma _{pr}(G)$-set, then $\mathrm {sd}_{\gamma _{pr}}(G)\le n-1.$

In this paper, we settle Conjecture 1 in the affirmative. The proof will be given in Section 3. But first it is useful to recall some results and give other lemmas and notations that are necessary for our investigation.

Proposition 1

[6] Let G be a connected graph of order $n\ge 3$ and $e=uv\in E(G)$. If $G^{\prime }$ is obtained from G by subdividing the edge e, then $\gamma _{pr}(G^{\prime })\ge \gamma _{pr}(G)$.

Proposition 2

[6] For every graph G of order $n\ge 3$, if $\gamma _{pr}(G)=2$ , then $1\le \mathrm {sd}_{\gamma _{pr}}(G)\le 3$.

Proposition 3

[6] If G contains either a strong support vertex or adjacent support vertices, then $\mathrm {sd}_{\gamma _{pr}}(G)\le 2$.

2 Preliminaries

We begin by giving some definitions. Let $k\ge 1$ be an integer, G a connected graph and v a vertex of G with $ecc(v)\ge k$. For each $0\le j\le k$, a jth weak-clique set of v is a subset $S\subseteq N_{j}(v)$ such that (i) for each $x\in S$, $N(x)\cap N_{j+1}(v)\ne \emptyset$, and (ii) for each pair of distinct vertices $x,y\in S$ , $N(x)\cap N(y)\cap N_{j+1}(v)=\emptyset$. The jth weak-clique number of v, $WC_{j}(v)$, is the maximum cardinality of a jth weak-clique set of v. We note that $WC_{0}(v)=1$ while if $WC_{1}(v)=0$, then $V(G)=N[v].$ Moreover, if v is a leaf of a graph of order at least three, then $WC_{1}(v)=1$.

For each $0\le j\le k$, let $S^{j}=\{x_{1}^{j},\ldots ,x_{\ell _{j}}^{j}\}$ be a jth weak-clique set of a vertex v and let ${N_{j}(v)}-S^{j}=\{x_{\ell _{j}+1}^{j},\ldots ,x_{s_{j}}^{j}\}$ if $N_{j}(v)-S^{j}\ne \emptyset$. A jth weak-separator of v is the set

$$\begin{aligned} \{x_{i}^{j}u\mid 1\le i\le \ell _{j}\;\mathrm {and}\;u\in N_{j+1}(v)\} \end{aligned}$$

if ${N_{j}(v)}=S^{j}$ and the set

$$\begin{aligned} \begin{array}{l} \{x_{i}^{j}u\mid 1\le i\le \ell _{j}\;\mathrm {and}\;u\in N_{j+1}(v)\}\cup \\ \left( \bigcup _{r=\ell _{j}+1}^{s_{j}}\{x_{r}^{j}u\mid u\in (N(x_{r}^{j})\cap N_{j+1}(v))\setminus (\cup _{i=1}^{r-1}N(x_{i}^{j}))\}\right) , \end{array} \end{aligned}$$

otherwise. If $WS_{j}(v)$ is a jth weak-separator of v for each j, then clearly

$$\begin{aligned} n(G)\ge 1+\sum _{j=0}^{k}\left| WS_{j}(v)\right| . \end{aligned}$$

Now, we can state some lemmas.

Lemma 1

Let G be a connected graph, and let $xy \in E(G)$. Let $G^{\prime }$ be a graph obtained from G by subdividing some edges. If there exists a minimum paired-dominating set D of $G^{\prime }$ with $x, y \in D$ and the partners of x and y are subdivision vertices, then $\gamma _{pr}(G) < \gamma _{pr}(G^{\prime })$.

Proof

Let F be the set of edges subdivided to obtain $G^{\prime }$ from G, and let $F_{1}$ be the set of all edges in F whose subdivision vertices in $G^{\prime }$ are not in D. Let $x^{\prime }$and $y^{\prime }$ be the subdivision vertices that are partners of x and y in D, respectively. In addition, suppose that $x^{\prime }$ and $y^{\prime }$ are resulting from the subdivision of the edges $e_{1},e_{2}$, respectively. If $G_{1}$ denotes the graph obtained from G by subdividing all edges in $F-(F_{1}\cup \{e_{1},e_{2}\})$, then the set $D\setminus \{x^{\prime },y^{\prime }\}$ in which x and y as partners is a PDS of $G_{1},$ and therefore $\gamma _{pr}(G)\le \gamma _{pr}(G_{1})<\gamma _{pr}(G^{\prime })$. $\square$

Lemma 2

Let G be a connected graph, and let xyz be a triangle. Let $G^{\prime }$ be a graph obtained from G by subdividing some edges, and assume that all edges incident with x and all edges in $\{yw \mid w \in N_G(y) \cap N_2(x)\}$ are subdivided. If there exists a minimum paired-dominating set D of $G^{\prime }$ with $x, y, z \in D$ and the partner of y is z, then $\gamma _{pr}(G) < \gamma _{pr}(G^{\prime })$.

Proof

Let $N_{G}(x)=\{y=x_{1},z=x_{2},\ldots ,x_{k}\},$ $N_{G}(y)\cap N_{2}(x)=\{y_{1},\ldots ,y_{r}\}$ and let F be the set of all subdivided edges of G. In particular, let $x_{1}^{\prime },\ldots ,x_{k}^{\prime }$ be the subdivision vertices of the edges $xx_{1},\ldots ,xx_{k},$ respectively, and assume, without loss of generality, that the edges $x_{1}y_{1},\ldots ,x_{1}y_{r}$ are subdivided with new vertices $y_{1}^{\prime },\ldots ,y_{r}^{\prime }$, respectively. Let D be a minimum paired-dominating set of $G^{\prime }$ containing x, y, z in which y and z are partners. Let $x_{i}^{\prime }$ be the partner of x and let $F^{\prime }\subseteq F$ be the set of edges whose subdivision vertices do not belong to D. Now, if $G_{1}$ denotes the graph obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{xx_{i}\}),$ then certainly the set $D-\{x_{1},x_{i}^{\prime }\}$ in which x and $x_{2}$ as partners, is a PDS of $G_{1}$ smaller than D and therefore yielding the desired result. $\square$

Lemma 3

Let G be a connected graph with $\gamma _{pr}(G)=4$ and let $v\in V(G)$ be a vertex of degree three with $N_{G}(v)= \{x_{1},x_{2},x_{3}\}$ such that $x_{2}x_{3}\in E(G)$, $N_{G}(x_{1})\not \subseteq N_{G}[v]$ and $x_{1}x_{2},x_{1}x_{3}\notin E(G)$. Then

$$\begin{aligned} \mathrm {sd}_{\gamma _{pr}}(G)\le 3+\deg (x_{1}). \end{aligned}$$

Proof

Since $N_{G}(x_{1})\not \subseteq N_{G}[v],$ assume that $N_{G}(x_{1})-N[v]=\{y_{1},\ldots ,y_{k}\}.$ Let $G^{\prime }$ be the graph obtained from G by subdividing the edges $vx_{1},vx_{2},vx_{3},x_{2}x_{3}$, $x_{1}y_{1},\ldots ,x_{1}y_{k}$ with new vertices $x_{1}^{\prime },x_{2}^{\prime },x_{3}^{\prime },z,y_{1}^{\prime },\ldots ,y_{k}^{\prime }$, respectively. Let D be a $\gamma _{pr}(G^{\prime })$-set. To dominate z, we may assume, without loss of generality, that $x_{2}\in D$. Suppose $\alpha$ is the partner of $x_{2}$.

Firstly, assume that $v\in D$ and let $\beta$ be the partner of v in D. If $\beta \ne x_{1}^{\prime }$, then to dominate $x_{1}$ we must have $D\cap \{x_{1},x_{1}^{\prime },y_{1}^{\prime },\ldots ,y_{k}^{\prime }\}\ne \emptyset$ and thus $\gamma _{pr}(G^{\prime })\ge 5>\gamma _{pr}(G)$. Hence we assume that $\beta =x_{1}^{\prime }$. If $x_{1}\in D$, then clearly $\gamma _{pr}(G^{\prime })\ge 5>\gamma _{pr}(G)$. Thus, let $x_{1}\not \in D$ . Then to dominate $y_{1}^{\prime },\ldots ,y_{k}^{\prime }$ we must have $\{y_{1},\ldots ,y_{k}\}\subseteq D.$ Now, if $k\ge 2$, then clearly $\gamma _{pr}(G^{\prime })\ge 5>\gamma _{pr}(G)$. Hence assume that $k=1,$ and thus $y_{1}\in D$. Now, if $y_{1}\ne \alpha$, then obviously $\gamma _{pr}(G^{\prime })\ge 5>\gamma _{pr}(G)$. Thus let $y_{1}=\alpha$. But then $D-\{v,x_{1}^{\prime }\}$ is a PDS of G,  and so $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$.

Secondly, assume that $v\not \in D$. Then to dominate $x_{1}^{\prime },x_{2}^{\prime },x_{3}^{\prime }$, we must have $x_{1},x_{2},x_{3}\in D$. Since $x_{2}$ and $x_{3}$ have different partners in D,  it follows that $\gamma _{pr}(G^{\prime })=|D|\ge 5>\gamma _{pr}(G).$ In either case, $\mathrm {sd}_{\gamma _{pr}}(G)\le 3+\deg (x_{1}).$ $\square$

Lemma 4

Let G be a connected graph of order at least three and let $v\in V(G)$ be a vertex of degree at least two. If v has a neighbor $x_{1}$ such that:

• (i) $x_{1}$ is an isolated vertex in G[N(v)],

• (ii) each vertex in $N(x_{1})$ has at least one neighbor in N(v) different from $x_{1}$,

• (iii) for each vertex $z\in N(v)-\{x_{1}\}$, $|N(x_{1})\cap N(z)\cap N_{2}(v)|\ge 1$,Then for any vertex $z\in N(v)-\{x_{1}\}$,

  $$\begin{aligned} \mathrm {sd}_{\gamma _{pr}}(G)\le |N(v)|+|N(x_{1})\cap N_{2}(v)|+{|N(z)\cap N_{2}(v)|.} \end{aligned}$$

Proof

Let $N(v)=\{x_{1},x_{2},\ldots ,x_{k}\}$, and assume that $N(x_{1})-N[v]$=$\{y_{1},\ldots ,y_{r}\}$ and $N(x_{2})-N[v]= \{y_{1}=z_{1},\ldots ,y_{\ell }=z_{\ell },z_{\ell +1},\ldots ,z_{s}\},$ where $\ell =|N(x_1)\cap N(x_2)\cap N_2(v)|$. Suppose $G^{\prime }$ is the graph obtained from G by subdividing the edges $vx_{1},\ldots ,vx_{k}$ with new vertices $x_{1}^{\prime },\ldots ,x_{k}^{\prime }$, respectively, the edges $x_{1}y_{1},\ldots ,x_{1}y_{r}$ with new vertices $y_{1}^{\prime },\ldots ,y_{r}^{\prime }$, respectively, and the edges $x_{2}z_{1}$, $\ldots , x_{2}z_{s}$ with new vertices $z_{1}^{\prime },\ldots ,z_{s}^{\prime }$, respectively. Let F be the set of all subdivided edges of G. Clearly $|F|=|N(v)|+ |N(x_{1})\cap N_{2}(v)|+|N(x_2)\cap N_{2}(v)|$.

Next, we shall show that $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$. Let D be a $\gamma _{pr}(G^{\prime })$-set and let $F_{1}$ be the set of all edges in F whose subdivision vertices in $G^{\prime }$ are not in D. We want to construct a PDS smaller than D of a graph $G_{i}$ obtained from G by subdividing the edges of a subset of F. Clearly, by Proposition 1 we will have $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G_{i})\ge \gamma _{pr}(G)$, which leads to the result. So let us consider the following two cases.

Case 1. $v\in D$.

Let $x_{i}^{\prime }$ be the partner of v in D. We first consider the case $x_{j}^{\prime }\in D$ with $j\ne i$. Then $x_{j}$ will be the partner of $x_{j}^{\prime }$. Let $G_{1}$ be the graph obtained from G by subdividing all edges in $F-\{vx_{i},vx_{j}\}$. By Lemma 1 we have $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G_{1})$ as desired. Hence we assume that $D\cap \{x_{1}^{\prime },\ldots ,x_{k}^{\prime }\}=\{x_{i}^{\prime }\}$. If $x_{1}\in D$ and $y_{j}^{\prime }$ is the partner of $x_{1}$ in D, then let $G_{2}$ be the graph obtained from G by subdividing all edges in $F-\{x_{1}v,vx_{i},x_{1}y_{j}\}$. Lemma 1 implies that $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G_{2})$ as desired. Hence we assume that $x_{1}\not \in D$. Then to dominate vertices $y_{1}^{\prime },\ldots ,y_{r}^{\prime }$ we must have $y_{1},\ldots ,y_{r}\in D$.

First let $x_{i}^{\prime }\ne x_{1}^{\prime }$. Since $N(x_{1})\cap N(v)=\emptyset$, to dominate $x_{1}$ we may assume that $y_{j}^{\prime }\in D$ for some j. Suppose $G_{3}$ is the graph obtained from G by subdividing all edges in $F-(F_1\cup \{vx_{i},x_{1}y_{j}\})$. Since each vertex in N(v) has a neighbor in $\{y_{1},\ldots ,y_{r}\}$, we deduce that $(D-\{v,x_{i}^{\prime },y_{j}^{\prime }\})\cup \{x_{1}\},$ with $x_{1}$ and $y_{j}$ as partners, is a PDS of $G_{3}$ smaller than D as desired.

Now let $x_{i}^{\prime }=x_{1}^{\prime }$. If $y_{j}^{\prime }\in D$ for some j, then let $G_{4}$ be the graph obtained from G by subdividing all edges in $F-\{vx_{1},\ldots ,vx_{k},x_{1}y_{j}\}$ and clearly $(D-\{v,x_{1}^{\prime },y_{j}^{\prime }\})\cup \{x_{1}\}$ with $x_{1}$ and $y_{j}$ as partners, is a PDS of $G_{4}$ smaller than D. Hence we assume that $D\cap \{y_{1}^{\prime },\ldots ,y_{r}^{\prime }\}=\emptyset$. If $x_{j}\in D$ for some $j\in \{2,\ldots ,k\}$, then let $G_{5}$ be the obtained from G by subdividing all edges in $F-\{vx_{1},\ldots ,vx_{k},x_{1}y_{1},\ldots ,x_{1}y_{r}\}$ and clearly $D-\{v,x_{1}^{\prime }\}$ is a PDS of $G_{5}$ smaller than D. Thus, suppose that $x_{2},\ldots ,x_{k}\not \in D$. To dominate $x_{2}$, we must have $z_{j}^{\prime }\in D$ for some j. In this case, let $G_{6}$ be the obtained from G by subdividing all edges in $F-\{vx_{1},\ldots ,vx_{k},x_{1}y_{1},\ldots ,x_{1}y_{r},x_{2}z_{j}\}$. Clearly $(D-\{v,x_{1}^{\prime },z_{j}^{\prime }\})\cup \{x_{2}\},$ with $x_{2}$ and $z_{j}$ as partners, is a PDS of $G_{6}$ smaller than D.

Case 2. $v\not \in D$.

Let $F_{1}$ be the set of all edges in F whose subdivision vertices in $G^{\prime }$ are not in D. To dominate the vertices $x_{1}^{\prime },\ldots ,x_{k}^{\prime }$, we must have $N_{G}(v)\subseteq D,$ in addition to $x_{i}^{\prime }\in D$ for some i to dominate v. If $x_{i}^{\prime }\ne x_{1}^{\prime }$ and $y_{j}^{\prime }$ is the partner of $x_{1}$, then let $G_{7}$ be the graph obtained from G by subdividing the edges in $F-(F_{1}\cup \{x_{1}y_{j},vx_{1},vx_{i}\}).$ It is easy to see that $(D-\{y_{j}^{\prime },x_{1},x_{i}^{\prime }\})\cup \{v\}$ with v and $x_{i}$ as partners, is a PDS of $G_{7}$ smaller than D (note that by item (ii), each vertex in $N_{G}(x_{1})-\{v\}$ has a neighbor in $N_{G}(v)-\{x_{1}\}$). Assume now that $x_{i}^{\prime }=x_{1}^{\prime }$. Thus $x_{1}^{\prime }$ and $x_{1}$ are partners in D. If $x_j^{\prime }\in D$ for some $j\ne 1$, then $x_j,x_j^{\prime }$ are partner in D and $(D-\{x_{j}^{\prime },x_{1},x_{1}^{\prime }\})\cup \{v\}$ with v and $x_{j}$ as partners, is a PDS of $G_{8}$ smaller than D where $G_8$ is the graph obtained from G by subdividing the edges in $F-(F_{1}\cup \{vx_{1},vx_{j}\}).$ First let $z_{j}^{\prime }$ be a partner of $x_{2}$, and let $G_{9}$ be the obtained from G by subdividing the edges of $F-(F_{1}\cup \{vx_{1},x_{2}z_{j}\}).$ Clearly $(D-\{x_{1},x_{1}^{\prime },z_{j}^{\prime }\})\cup \{v\}$ with v and $x_{2}$ as partners is a PDS of $G_{9}$ smaller than D. Finally, assume that $x_{j}$ is the partner of $x_{2}$ in D,  for some $j\in \{3,\ldots ,k\}$. Let $G_{10}$ be obtained from G by subdividing the edges of $F-(F_{1}\cup \{vx_{1}\})$. Clearly $(D-\{x_{1},x_{1}^{\prime },x_{2}\})\cup \{v\}$ with v and $x_{j}$ as partners is a PDS of $G_{10}$ smaller than D,  and this completes the proof. $\square$

Lemma 5

Let G be a connected graph of order at least 4 and let $v\in V(G)$ be a vertex of degree at least two.

• (i) If $WC_{1}(v)=0$, then $\mathrm {sd}_{\gamma _{pr}}(G)\le 3$.

• (ii) If $WC_{1}(v)\ge 2$ and the induced subgraph G[N(v)] is isolated-free, then $\mathrm {sd}_{\gamma _{pr}}(G)\le \deg (v)+|N_{2}(v)|+|N_{3}(v)|\le n-1$.

• (iii) If the induced subgraph G[N(v)] has an isolated-vertex z and there is a weak-clique set of v, $S^{1}$, such that $z\in S^{1}$ and $|S^{1}|\ge 2$, then $\mathrm {sd}_{\gamma _{pr}}(G)\le \deg (v)+|N_{2}(v)|+|N_{3}(v)|\le n-1$.

Proof

(1)- If $WC_{1}(v)=0$, then $V(G)=N[v]$ and so $\gamma _{pr}(G)=2$ and we deduce from Proposition 2 that $\mathrm {sd}_{\gamma _{pr}}(G)\le 3$.

To prove the remaining two items, let $N(v)=\{x_{1},x_{2},\ldots ,x_{k}\}$ , $S^{1}$ be a 1th weak-clique set of v of size $WC_{1}(v)$ and let $WS_{1}(v)$ be a 1th weak-separator of v. We may assume, without loss of generality, that $S^{1}=\{x_{1},x_{2},\ldots ,x_{\ell }\}$. Moreover, if $N_{3}(v)\ne \emptyset ,$ then let $S^{2}$ be a 2th weak-clique set of v of size $WC_{2}(v)$ and let $WS_{2}(v)$ be a 2th weak-separator of v.

(2)- Let $WC_{1}(v)\ge 2$ and let the induced subgraph G[N(v)] be isolated-free. Suppose $N(x_{1})-N[v]=\{y_{1},\ldots ,y_{r}\}$ and $N(x_{2})-N[v]=\{z_{1},\ldots ,z_{s}\}$. Since $WC_{1}(v)\ge 2$, we have $(N(x_{1})-N[v])\cap (N(x_{2})-N[v])=\emptyset$. Let $G^{\prime }$ be the graph obtained from G by subdividing the edges $vx_{1},\ldots ,vx_{k}$ with subdivision vertices $x_{1}^{\prime },\ldots ,x_{k}^{\prime }$, respectively, the edges $x_{1}y_{1},\ldots ,x_{1}y_{r}$ with subdivision vertices $y_{1}^{\prime },\ldots ,y_{r}^{\prime }$, respectively, the edges $x_{2}z_{1},\ldots ,x_{2}z_{s}$ with subdivision vertices $z_{1}^{\prime },\ldots ,z_{s}^{\prime }$, respectively, and all other edges in $WS_{1}(v)\cup WS_{2}(v)$. Set $F=\{vx_{1},\ldots ,vx_{k}\}\cup WS_{1}(v)\cup WS_{2}(v)$. Note that $\left| F\right| = \deg (v)+|N_{2}(v)|+|N_{3}(v)|.$ Let D be a $\gamma _{pr}(G^{\prime })$-set and let $F_{1}$ be the set of all edges of G whose subdivision vertices in $G^{\prime }$ are not in D. We consider two cases.

Case 1. $v\in D$.

Let $x_{i}^{\prime }$ be the partner of v in D. First let $D\cap S^{1}\ne \emptyset$. We may assume, without loss of generality, that $x_{1}\in D\cap S^{1}$, and let $\alpha$ be the partner of $x_{1}$ in D. If $\alpha \in \{x_{1}^{\prime },y_{1}^{\prime },\ldots ,y_{r}^{\prime }\}$, then by Lemma 1 we have $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G),$ and the desired result follows. Hence we assume that $\alpha \in N_{G}(v)$. Let $G_{1}$ be the graph obtained from G by subdividing the edges in $F-(F_{1}\cup \{vx_{i}\})$. Clearly $D-\{x_{1},x_{i}^{\prime }\},$ with v and $\alpha$ as partners, is a PDS of $G_{1}$ smaller than D. In the sequel we can assume that $D\cap S^{1}=\emptyset$. It follows that $N_{2}(v)\cap \left( \bigcup _{i=1}^{\ell }N_{G}(x_{i})\right) \subseteq D$.

Now we prove that $N_G(v) \cap D = \emptyset$. If $x_{j}\in N_{G}(v)\cap D$ and its partner $\alpha$ is a subdivision vertex, then we deduce from Lemma 1 that $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$. If $x_{j}\in N_{G}(v)\cap D$ and its partner $\alpha$ belongs to N(v), then let $\alpha =x_{p}$ and let $G_{1}^{\prime \prime }$ be the graph obtained from G by subdividing all edges in $F-(F_{1}\cup \{vx_{i}\}).$ Assume, without loss of generality, that $p>j$. We claim that the set $D^{\prime }=D-\{\alpha ,x_{i}^{\prime }\}$ with v and $x_{j}$ as partner, is a PDS of $G_{1}^{\prime \prime }$. It is enough to show that any vertex y dominated by $\alpha$ in G, is dominated by $D^{\prime }$ in $G_{1}^{\prime \prime }$. We note that any vertex y in $N(v)-D$ dominated by $\alpha$ in $G^{\prime }$, is simply dominated by v in $G_{1}^{\prime \prime }$ (since the edge vy belongs to $F_{1}$). On the other hand, any subdivision vertex adjacent to $\alpha$ in $G_{1}^{\prime \prime }$ belongs to $D^{\prime }$ (by definition of $G_{1}^{\prime \prime }$). Now assume that $y\in N_{2}(v)$ and is dominated by $\alpha$ in $G^{\prime }$. Let m be the smallest integer such that $x_{m}y\in E(G)$. Obviously the edge $x_{m}y$ is subdivided in $G^{\prime }$ by the definition of 1th weak separator. Let z be the subdivision vertex of the edge $x_{m}y$. To paired-dominate z, we must have $D\cap \{y,x_{m},z\}\ne \emptyset$. Now if $y\in D$ or $z\in D$, then we are done. Otherwise, $x_{m}\in D$ and $z\notin D$ and thus the edge $yx_{m}\in E(G_{1}^{\prime \prime })$ implying that y is dominated by $x_{m}\in D^{\prime }$ in $G_{1}^{\prime \prime }$. Hence $D^{\prime }$ is a PDS of $G_{1}^{\prime \prime }$. For the remaining situation, if $x_{j}\in N_{G}(v)\cap D$ and its partner $\alpha$ belongs to $N_{2}(v)$, then let $G_{2}$ be the graph obtained from G by subdividing all edges in $F-(F_{1}\cup \{vx_{i}\}).$ We also claim that $D_1=D-\{\alpha ,x_{i}^{\prime }\}$ with v and $x_{j}$ as partner, is a PDS of $G_{2}$. To see this, it is enough to show that any vertex y dominated by $\alpha$ in $G^{\prime }$, is dominated by $D^{\prime }$ in $G_{2}$. Clearly, any vertex y in $N(v)-D$ dominated by $\alpha$ in $G^{\prime }$ , is dominated by v in $G_{2}$ (since as above, the edge $vy\in F_{1}$) . Also, any subdivision vertex adjacent to $\alpha$ in $G_{2}$ belongs to $D_1$ (by the definition of $G_{2}$). Now, if $y\in N_{2}(v)$, then by the definition of 1th weak separator y is adjacent to a subdivision vertex $\beta$ of an edge yw where $w\in N(v)$. Now to paired-dominate $\beta$ in $G^{\prime }$ we must have $|D\cap \{w,y,\beta \}|\ge 1$. Clearly $D\cap \{\beta ,w,y\}=D_1\cap \{\beta ,w,y\}$ and so y is dominated by a vertex of $D_1$ in $G_{2}$ as desired. Finally, we assume that $y\in N_{3}(v)$. By the definition of 2th weak separator, y is adjacent to a subdivision vertex $\beta$ of an edge yw where $w\in N_{2}(v)$. To paired-dominate $\beta$ we must have $|D\cap \{w,y,\beta \}|\ge 1$. If $y\in D$ or $\beta \in D$, then we are done. Otherwise, $w\in D$ and $\beta \notin D$ and thus the edge $wy\in E(G_{2})$ implying that y is dominated by $w\in D_1$ in $G_{2}.$

Hence assume that $N_{G}(v)\cap D=\emptyset$. It follows that the partner of v, namely $x_{i}^{\prime }$, is the unique vertex of $\{x_{1}^{\prime },\ldots ,x_{k}^{\prime }\}$ belonging to D. Suppose, without loss of generality, that $x_{i}^{\prime }\ne x_{1}^{\prime }.$ To dominate $x_{1}$ we must have for some $j\in \{1,\ldots ,r\},$ $y_{j}^{\prime }\in D$ paired with $y_{j}.$ Let $G_{3}$ be the graph obtained from G by subdividing the edges in $F-(F_{1}\cup \{vx_{i},x_{1}y_{j}\})$. Note that $vx_{1}\in F_{1}.$ We claim that $D^{\prime }=(D-\{x_{i}^{\prime },y_{j},y_{j}^{\prime }\})\cup \{x_{1}\}$ with v and $x_{1}$ as partners is a PDS of $G_{3}$ smaller than D. It is enough we show that any vertex u dominated by $y_{j}$ in G, is dominated by $D^{\prime }$ in $G_{3}$. If $u\in N(v)$, then u is dominated by v in $G_3$. If $u\in N_{2}(v)$, then by definition of 1th weak separator u is adjacent to a subdivision vertex $\beta$ of an edge uw where $w\in N(v)$. Now to paired-dominate $\beta$ we must have $|D\cap \{w,u,\beta \}|\ge 1$. Since $w\not \in D$, we have $u\in D$ and thus $u\in D^{\prime }$ as desired. Hence assume that $u\in N_{3}(v)$. Clearly $u\ne y_{j}$. By definition of 2th weak separator u is adjacent to a subdivision vertex $\beta$ of an edge uw where $w\in N_{2}(v)$. To paired-dominate $\beta$ we must have $|D\cap \{w,u,\beta \}|\ge 1$. If $u\in D$ or $\beta \in D$, then we are done. Otherwise, u is dominated by w in $D^{\prime }$ as desired.

Case 2. $v\not \in D$.

To dominate the vertices $x_{1}^{\prime },\ldots ,x_{k}^{\prime }$, we must have $N_{G}(v)\subseteq D.$ Also, D must contain $x_{i}^{\prime }$ for some i to dominate v. Since $WC_{1}(v)\ge 2,$ we may assume that $x_{i}^{\prime }\ne x_{1}^{\prime }.$ Let $G_{4}$ be the graph obtained from G by subdividing the edges in $F-(F_{2}\cup \{vx_{i}\})$, and consider the set $D_{1}=D-\{x_{i},x_{i}^{\prime }\}.$ Note that since G[N(v)] is isolate-free, vertex $x_{i}$ has a neighbor in N(v) and such a neighbor belongs to $D_{1}.$ Now let $u\in N_{2}(v)$ be a neighbor of $x_{i}.$ If the edge $x_{i}u$ is subdivided in $G^{\prime }$ (note that $x_{i}u$ may belong or not to $F_{1})$, then clearly u is a dominated by $D_{1}.$ Hence we assume that $x_{i}u$ is not subdivided in $G^{\prime }.$ We deduce that u is adjacent to some vertex in $\{x_{1},\ldots ,x_{i-1}\}$. Let j be the smallest integer such that $ux_{j}\in E(G).$ Then the edge $x_{j}u$ should be subdivided (with new vertex w) according to the definition of weak-separator. Hence u is dominated by w or $x_{j}$ in $D_{1}$. Therefore, we conclude that $D_{1}$ is PDS of $G_{4}$ smaller than D.

(3)- We proceed similarly as for item (2), in particular, let $G^{\prime }$ and D as defined above. Assume, without loss of generality, that $z=x_{1}$. In the case $v\in D$, the proof is the same as in (2). Hence let us assume that $v\not \in D$. To dominate the vertices $x_{1}^{\prime },\ldots ,x_{k}^{\prime }$, we must have $N_{G}(v)\subseteq D.$ Also, D must contain $x_{i}^{\prime }$ for some i to dominate v. If $x_{i}$ is not an isolated vertex in G[N(v)], then the result follows as in Case 2 of item (2). Hence, let $x_{i}$ be an isolated vertex in G[N(v)]. If $x_{i}\ne x_{1}$ and $z^{\prime }$ is the partner of $z=x_{1}$ resulting from the subdivision of the edge e, then let $G_{5}$ be the graph obtained from G by subdividing the edges in $F-(F_{1}\cup \{vx_{i},e\})$. Set $D_{2}=(D-\{x_{i},x_{i}^{\prime },z^{\prime }\})\cup \{v\}$ with v and $x_{1}$ as partners. Also, if $x_{i}$ has a neighbor u in $N_{2}(v)$ such that the edge $x_{i}u$ is not subdivided in $G^{\prime }$, then by a similar argument to that used in Case 2 of item (2), we can see that there is a vertex $x_{j}\in S^{1}$ such that edge $x_{j}u$ is subdivided with a new vertex w, and thus u is either dominated by w (if $x_{j}u\notin F_{1}$) or $x_{j}$ (if $x_{j}u\in F_{1}$). Therefore, $D_{2}$ is a PDS of $G_{5}$ smaller than D. Hence assume that $x_{1}=x_{i}$. Since $x_{2}\in D$, let y be the partner of $x_{2}$. If y is resulting from the subdivision of some edge e, then let $G_{6}$ be the graph obtained from G by subdividing the edges in $F-(F_{1}\cup \{vx_{1},e\})$. Clearly $(D-\{x_{1},y,x_{1}^{\prime }\})\cup \{v\}$ with v and $x_{2}$ as partners is a PDS of $G_{6}$ smaller than D. Finally, assume that $y\in N(x).$ In this case, let $G_{7}$ be the graph obtained from G by subdividing the edges in $F-(F_{1}\cup \{vx_{1}\})$. Note that $\{vx_{2},vy\}\subset F_{1}$, and thus $(D-\{x_{2},x_{1},x_{1}^{\prime }\})\cup \{v\}$ with v and y as partners is a PDS of $G_{7}$ smaller than D, which completes the proof. $\square$

3 Proof of Conjecture 1

Now, we are ready to state our main result which settles Conjecture 1.

Theorem 1

For every connected graph G of order $n\ge 3$, $\mathrm {sd}_{\gamma _{pr}}(G)\le n-1$.

Proof

If $\gamma _{pr}(G)=2,$ then the result is immediate from Proposition 2. Hence we may assume that $\gamma _{pr}(G)\ge 4$. If G contains a strong support vertex or two adjacent support vertices, then the result follows from Proposition 3. Thus we may assume that G has at least one vertex x of degree at least 2 which is not a support vertex. If such a vertex x satisfies one of the conditions of Lemma 5, then we are done. Hence we may assume that for each non-support vertex x of G with $\deg (x)\ge 2$, either $WC_{1}(x)=1$ or $WC_{1}(x) \ge 2$ and x has a neighbor y such that y is an isolated vertex in G[N(x)] and y belongs no 1th weak-clique S with $|S|\ge 2$ . Among all non-support vertices of G with degree at least two, let v be one having maximum degree. Moreover, if $|WC_{1}(v)|=1$, then among the neighbors of v, let $x_{1}$ be one chosen so that:

($C_1$):

$x_1$ has exactly one neighbor in $N_2(v)$.

($C_{2}$):

If ($C_{1}$) does not occur, then $x_{1}$ is an isolated vertex in G[N(v)].

($C_{3}$):

If ($C_{1}$) and ($C_{2}$) do not occur, then $x_{1}$ is an arbitrary vertex in N(v) so that $\left| N(x_{1})\cap N_{2}(v)\right| \ge 1$.

Otherwise, among all isolated vertices in G[N(v)] belonging to no 1th weak-clique set of size at least two, let $x_{1}$ be one chosen so that $|N(x_{1})\cap N_{2}(v)|$ is minimized.

Assume that $N(v)=\{x_{1},\ldots ,x_{k}\}$ and $N(x_{1})\cap N_{2}(v)=\{y_{1},\ldots ,y_{r}\}$. Let $S^{0}=\{v\},$ $S^{j}$ be a jth weak-clique set of v and $WS_{j}(v)$ be a jth weak-separator of v corresponding to $S^{j},$ where $j\in \{1,2,3\}$. Consider the following two cases.

Case 1. $WC_{1}(v)=1.$

Hence $S^{1}=\{x_{1}\}.$ Let $G^{\prime }$ be the graph obtained from G by subdividing the edges $vx_{1},\ldots ,vx_{k}$ with subdivision vertices $x_{1}^{\prime },\ldots ,x_{k}^{\prime }$, respectively, the edges $x_{1}y_{1},\ldots ,x_{1}y_{r}$ with subdivision vertices $y_{1}^{\prime },\ldots ,y_{r}^{\prime }$, respectively, and all the other edges in $WS_{1}(v)\cup WS_{2}(v)\cup WS_{3}(v)$. We show that$\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$. Let D be a $\gamma _{pr}(G^{\prime })$-set. Also, let F be the set of all subdivided edges of G and $F^{\prime }\subseteq F$ be the set of edges whose subdivision vertices do not belong to D. We distinguish two situations.

Subcase 1.1. $v\in D$.

Let $x_{i}^{\prime }$ be the partner of v. If $x_{j}^{\prime }\in D$ for some $j\ne i$, then $x_{j}$ is its partner in D and by Lemma 1 we have $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$. Thus, we may assume that

$$\begin{aligned} D\cap \{x_{1}^{\prime },\ldots ,x_{k}^{\prime }\}=\{x_{i}^{\prime }\}. \end{aligned}$$

(1)

If $x_{1}\in D$ and $y_{j}^{\prime }$ is the partner of $x_{1}$ for some j , then Lemma 1 implies that $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$. If $x_{1}\in D$ and $x_{j}$ is the partner of $x_{1}$ for some $j\in \{2,\ldots ,k\}$, then we deduce from Lemma 2 that $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$. Hence we may assume that $x_{1}\not \in D$. It follows that

$$\begin{aligned} \{y_{1},\ldots ,y_{r}\}\subseteq D. \end{aligned}$$

To dominate $x_{1}$, we must have $D\cap \{x_{1}^{\prime },x_{2},\ldots ,x_{k},y_{1}^{\prime },\ldots ,y_{r}^{\prime }\}\ne \emptyset$. First, if $y_{j}^{\prime }\in D$ for some j, then $(D-\{y_{j},y_{j}^{\prime },x_{i}^{\prime }\})\cup \{x_{1}\}$ with v and $x_{1}$ as partners, is a PDS of the graph $G_{1}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{i},x_{1}y_{j}\})$ smaller than D (a similar discussion to that of item 2 of Lemma 5 can be applied for this situation). Suppose now that $x_{j}\in D$ for some $2\le j\le k$ and let $\beta$ be the partner of $x_{j}$. If $\beta$ is a subdivision vertex of an edge, then by Lemma 1 we have $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$. Assume that $\beta =y_{\ell }$ for some $\ell$. We claim that $D^{\prime }=D-\{y_{\ell },x_{i}^{\prime }\}$ with v and $x_{j}$ as partners, is a PDS of the graph $G_{2}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{i}\})$. Note that any vertex y in $N(v)-D$ is dominated by v (since the edge vy belongs to $F_{1}\cup \{vx_i\}$). Now assume that $y\in N_{2}(v)$ and is dominated by $y_{\ell }$ in $G^{\prime }$. Let m be the smallest integer such that $x_{m}y\in E(G)$ . Obviously the edge $x_{m}y$ is subdivided in $G^{\prime }$ by the definition of 1th weak separator. Let z be the subdivision vertex of the edge $x_{m}y$. To paired-dominate z, we must have $D\cap \{y,x_{m},z\}\ne \emptyset$. Now if $y\in D$ or $z\in D$, then we are done. Otherwise, $x_{m}\in D$ and $z\notin D$ and thus the edge $yx_{m}\in E(G_{2})$ implying that y is dominated by $x_{m}\in D^{\prime }$ in $G_{2}$.Finally, we assume that $y\in N_{3}(v)$. By the definition of 2th weak separator, y is adjacent to a subdivision vertex $\eta$ of an edge yw where $w\in N_{2}(v)$. To paired-dominate $\eta$ we must have $|D\cap \{w,y,\eta \}|\ge 1$. If $y\in D$ or $\eta \in D$, then we are done. Otherwise, $w\in D$ and $\eta \notin D$ and thus the edge $wy\in E(G_{2})$ implying that y is dominated by $w\in D^{\prime }$ in $G_{2}.$ If $\beta =x_{\ell }$, then $D-\{x_{j},x_{i}^{\prime }\}$ with v and $x_{\ell }$ as partners, is a PDS of the graph $G_{3}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{i}\})$ smaller than D. Assume now that $x_{i}^{\prime }$ dominates $x_{1},$ that is $x_{1}^{\prime }=x_{i}^{\prime }$. Using a similar argument as above, we may assume that

$$\begin{aligned} D\cap N(v)=\emptyset . \end{aligned}$$

(2)

If there is an edge $x_{j}y\in WS_{1}(v)$ whose subdivision vertex is in D , then as above we can get the result. Hence we assume that no subdivision vertex of any edge of $WS_{1}(v)$ belongs to D and so we have

$$\begin{aligned} N_{2}(v)\subseteq D. \end{aligned}$$

Since $i=1$, we deduce from (1), (2) and above assumption that each $x_{j}\;(2\le j\le k)$ is dominated by a vertex in $N_{2}(v)$ and we conclude from $|WC_{1}(v)|=1$ that each vertex in N(v) has a neighbor in $\{y_{1},\ldots ,y_{r}\}$. Let $\beta _{j}$ be the partner of $y_{j}$ in D for each $j\in \{1,\ldots ,r\}$. If $\beta _{j}$ is a subdivision vertex of an edge e for some j, then the set $(D-\{\beta _{j},v,x_{1}^{\prime }\})\cup \{x_{1}\}$ with $x_{1}$ and $y_{j}$ as partners, is a PDS of the graph $G_{4}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{1},x_{1}y_{j},e\})$ smaller than D. If $\beta _{j}\in N_{2}(v)-N_{G}(x_{1})$, then the set $D^{\prime }=D-\{x_{i}^{\prime },v,\beta _{j}\}\cup \{x_{1}\}$ with $x_{1}$ and $y_{j}$ as partners, is a PDS of the graph $G_{5}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{1}\})$ smaller than D. We note that in the previous situation, each vertex in $N_{1}(v)$ has a neighbor in $\{y_{1},\ldots ,y_{r}\}$ (since $D\cap N(v)=\emptyset$) and so it is dominated. Moreover, each vertex in $N_{2}(v)-\{\beta _{j}\}$ is in $D^{\prime }$, and if a vertex $y\in N_{3}(v)$ is adjacent to $\beta _{j}$, then by definition, y is on a subdivided edge $e_{1}$ between y and $N_{2}(v)$ and to dominate the subdivision vertex one of the endvertices of $e_{1}$ must belong to D and so y is dominated by $D^{\prime }$). If $\beta _{j}\in N_{3}(v)$, then the set $D^{\prime }=(D-\{x_{i}^{\prime },v,\beta _{j}\})\cup \{x_{1}\}$ with $x_{1}$ and $y_{j}$ as partners, is a PDS of the graph $G_{6}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{1}\})$, smaller than D (note that $N_{2}(v)\subseteq D^{\prime }$, $\beta _{j}$ is dominated by $y_{j}$, each vertex z in $N_{3}(v)-\{\beta _{j}\}$ is either an endvertex of a subdivided edge $e_{1}$ between z and $N_{2}(v)$ and so z is dominated by the subdivision vertex of $e_{1}$ or the other end-point of $e_{1}$ in $G_{6}$, and finally if a vertex $z\in N_{4}(v)$ was dominated by $\beta _{j}$ , then z is adjacent to an endvertex of a subdivided edge $e_{2}$ between z and $N_{3}(v)$ and so z is dominated by either the subdivision vertex of $e_{2}$ or the other endvertex of $e_{2}$. Finally let $\beta _{j}\in \{y_{1},y_{2},\ldots ,y_{r}\}$ for each $1\le j\le r$. Hence $x_{1}$ has at least two neighbors in $N_{2}(v)$. We shall show that $D^{\prime }=(D-\{v,x_{i}^{\prime },\beta _{1}\})\cup \{x_{1}\}$ with $x_{1}$ and $y_{1}$ as partners, is a PDS of the graph $G_{7}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{i},x_{1}y_{1}\})$, smaller than D. As above we can see that every vertex in $N_{2}(v)\cup N_{3}(v)$ is dominated by $D^{\prime }$ in $G_{7}$. Now let $y\in N_{1}(v)$ be a vertex which was dominated by $\beta _{1}$ in $G^{\prime }$. By the choice of $x_{1}$, we have that y has at least two neighbors in $N_{2}(v)$. If $yz\in E(G)$ where $z\in N_{2}(v)-\{\beta _{1}\}$, then y will be dominated by z or the subdivision vertex of the edge yz in $D^{\prime }$. Thus $D^{\prime }$ is a PDS of the graph $G_{7}$ smaller than D.

Subcase 1.2. $v\not \in D$.

Clearly $N(v)\subseteq D$, and to dominate v we must have for some i, $x_{i}^{\prime }\in D$ paired with $x_{i}.$ If $x_{i}$ has a neighbor in N(v) , then one can easily see that $D-\{x_{i},x_{i}^{\prime }\}$ is a PDS of the graph $G_{8}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{i}\}),$ smaller than D. Hence we assume that $x_{i}$ has no neighbor in N(v). Since v is not a support vertex, we have $N(x_i)\cap N_2(v)\ne \emptyset$.

First let $x_{1}\ne x_{i}$ and let $\beta$ be the partner of $x_{1}$ in D . If $\beta$ is a subdivision vertex of an edge e, then it is easy to see that $(D-\{x_{i},x_{i}^{\prime },\beta \})\cup \{v\}$ with $x_{1}$ and v as partners, is a PDS of the graph $G_{9}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{i},vx_{1},e\})$ smaller than D. Hence we assume that $\beta \in N(v)$. Since $x_{i}$ has no neighbor in N(v),  by the choice of $x_{1}$, $x_{1}$ has exactly one neighbor in $N_{2}(v)$. If $\beta =x_{j}$ for some $j\ne 1$ and $N(x_{j})\subseteq N(v)$ , then we can see that $(D-\{x_{i},x_{i}^{\prime },x_{j}\})\cup \{v\}$ with $x_{1}$ and v as partners, is a PDS of the graph $G_{10}$ obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{i}\})$ smaller than D . If $\beta =x_{j}$ for some $j\ne 1$ and $N(x_{j})\not \subseteq N(v)$, then $x_{j}y_{1}\in E(G)$ and we can see that $(D-\{x_{i},x_{i}^{\prime },x_{1}\})\cup \{y_{1}\}$ with $x_{j}$ and $y_{1}$ as partners, is a PDS of the graph $G_{10}$ smaller than D.

Now let $x_{1}=x_{i}$. If $y_{j}\in D$ for some $j\in \{1,\ldots ,r\}$, then let $G_{11}$ be the graph obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{1}\})$. Clearly $D-\{x_{1},x_{1}^{\prime }\}$ is a PDS of $G_{11}$ smaller than D. Hence we assume that $D\cap \{y_{1},\ldots ,y_{r}\}=\emptyset$, and thus $D\cap \{y_{1}^{\prime },\ldots ,y_{r}^{\prime }\}=\emptyset$. If some $y_{j}$ has no neighbor in $N(v)-\{x_{1}\}$, then by choosing $x_{1}$ instead of v we will be in a position of Item 3 form Lemma 5 and the result follows. Hence we can assume that each $y_{j}$ has a neighbor in $N(v)-\{x_{1}\},$ and thus $x_{1}$ is not a support vertex. Now, for each $j\in \{2,\ldots ,k\},$ let $\beta _{j}$ be the partner of $x_{j}$ in D. If $\beta _{j}$ is a subdivision vertex of an edge $e\in E(G)$, then let $G_{12}$ be the graph obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{e,vx_{j},vx_{1}\})$. Clearly $(D-\{x_{1},x_{1}^{\prime },\beta _{j}\})\cup \{v\}$ with v and $x_{j}$ as partners, is a PDS of $G_{12}$ smaller than D. If $\beta _{j}\in N_{2}(v)$, then let $G_{13}$ be obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{j},vx_{1}\})$. As in Subcase 1.1, we can see that $(D-\{x_{1},x_{1}^{\prime },\beta _{j}\})\cup \{v\}$ with v and $x_{j}$ as partners, is a PDS of $G_{13}$ smaller than D. Thus we assume that $\beta _{j}\in N_{1}(v)$ for each $j\in \{2,\ldots ,k\}$. If some $x_{j}$ has no a private neighbor in $N_{2}(v)\cap N(x_{1})$ with respect to $N(v)-\{x_{1}\}$, then let $G_{14}$ be the graph obtained from G by subdividing all edges in $F-(F^{\prime }\cup \{vx_{j},vx_{1}\})$. Clearly $(D-\{x_{1},x_{1}^{\prime },x_{j}\})\cup \{v\}$ with v and $\beta _{j}$ as partners, is a PDS of $G_{14}$ smaller than D. Thus we may assume that each $x_{j}$ has a private neighbor in $N_{2}(v)\cap N(x_{1})$ with respect to $N(v)-\{x_{1}\}$. Therefore, $\deg (x_{1})\ge \deg (v)$. But since $x_{1}$ is not a support vertex with $|WC_{1}(v)|=1$, we deduce from the choice of v that $\deg (x_{1})=\deg (v)$. It follows that for each $j\in \{2,\ldots ,k\}$, $|N_{2}(v)\cap N_{G}(x_{1})\cap N_{G}(x_{j})|=1$. Now, Lemma 4 implies that

$$\begin{aligned} {\mathrm {sd}_{\gamma _{pr}}(G)\le |N_{G}(v)|+|N_{2}(v)\cap \left( N_{G}(x_{1})\cup N_{G}(x_{2})\right) |+1.} \end{aligned}$$

(3)

If $\gamma _{pr}(G)>4$, then we must $|N_{2}(v)\setminus \left( N_{G}(x_{1})\cup N_{G}(x_{2})\right) |\ge 1$ and we deduce from the inequality (3) that $sd_{\gamma _{pr}}(G)\le n-1$. Hence we assume that $\gamma _{pr}(G)=4$. If $\deg (v)\ge 4$, then we conclude from $N(v)\subseteq D$ and the fact that $x_{1}$ is isolated in G[N(v)] that $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$. Thus $\deg (v)=3$, and therefore the result follows from Lemma 3.

Case 2. $WC_{1}(v)\ge 2,$ and v has a neighbor y which is isolated in G[N(v)] and y belongs to no 1th weak-clique S with $|S|\ge 2$.

The proof is similar to Case 1 and so we omit the details. But here are a few hints.

We first consider the graph $G^{\prime }$ obtained from G by subdividing the edges $vx_{1},\ldots ,vx_{k},$ $x_{1}y_{1},\ldots ,x_{1}y_{r}$ and all the other edges in $WS_{1}(v)\cup WS_{2}(v)\cup WS_{3}(v)$. Sets D, F and $F^{\prime }$ are defined as in Case 1. Subsequently, we distinguish two subcases according to whether or not v belongs to D. In particular, the subcase $v\in D,$ will be divided into two situations: $|N_{2}(v)\cap N(x_{1})\cap N(x_{j})|=1$ for some $j\in \{2,\ldots ,k\}$ or $|N_{2}(v)\cap N(x_{1})\cap N(x_{j})|\ge 2$ for each $j\in \{2,\ldots ,k\}$. The goal is to show in either situation of the proof that $\gamma _{pr}(G^{\prime })>\gamma _{pr}(G)$. $\square$

We conclude this paper with the following conjecture.

Conjecture 2

For every connected graph G of order $n\ge 3$, $\mathrm {sd} _{\gamma _{pr}}(G)\le \gamma _{pr}(G)+1$.

It is well-known that connected graphs of order $n\ge 6$ with minimum degree at least two have paired-domination number bounded above by 2n/3. Therefore for such class of graphs the bound of Theorem 1 would be improved if Conjecture 2 is true.