ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P2.04 / 231–248
https://doi.org/10.26493/1855-3974.2522.eb3
(Also available at http://amc-journal.eu)
Paired domination stability in graphs
Aleksandra Gorzkowska
AGH University, Department of Discrete Mathematics,
al. Mickiewicza 30, 30-059 Krakow, Poland
Michael A. Henning
Department of Mathematics and Applied Mathematics, University of Johannesburg,
Auckland Park, 2006 South Africa
Monika Pilśniak
AGH University, Department of Discrete Mathematics,
al. Mickiewicza 30, 30-059 Krakow, Poland
Elżbieta Tumidajewicz *
AGH University, Department of Discrete Mathematics,
al. Mickiewicza 30, 30-059 Krakow, Poland, and
Department of Mathematics and Applied Mathematics, University of Johannesburg,
Auckland Park, 2006 South Africa
Received 29 December 2020, accepted 16 July 2021, published online 27 May 2022
Abstract
A set S of vertices in a graph G is a paired dominating set if every vertex of G is
adjacent to a vertex in S and the subgraph induced by S contains a perfect matching (not
necessarily as an induced subgraph). The paired domination number, γpr(G), of G is the
minimum cardinality of a paired dominating set of G. A set of vertices whose removal from
G produces a graph without isolated vertices is called a non-isolating set. The minimum
cardinality of a non-isolating set of vertices whose removal decreases the paired domination
number is the γ−pr-stability of G, denoted st
−
γpr(G). The paired domination stability of G
is the minimum cardinality of a non-isolating set of vertices in G whose removal changes
the paired domination number. We establish properties of paired domination stability in
graphs. We prove that if G is a connected graph with γpr(G) ≥ 4, then st−γpr(G) ≤ 2∆(G)
where ∆(G) is the maximum degree in G, and we characterize the infinite family of trees
that achieve equality in this upper bound.
Keywords: Paired domination, paired domination stability.
*Corresponding author.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
232 Ars Math. Contemp. 22 (2022) #P2.04 / 231–248
Math. Subj. Class. (2020): 05C69
1 Introduction
In 1983 Bauer, Harary, Nieminen and Suffel [3] introduced and studied the concept of
domination stability in graphs. Stability for other domination type parameters has been
studied in the literature. For example, total domination stability, 2-rainbow domination
stability, exponential domination stability, Roman domination stability are studied in [1, 2,
12, 15, 16], among other papers. In this paper we study the paired version of domination
stability.
Let G = (V,E) be a graph with vertex set V = V (G) and edge set E = E(G). Two
vertices u and v are neighbors if they are adjacent, that is, if uv ∈ E. A dominating set of G
is a set D of vertices such that every vertex in V (G)\D has a neighbor in D. The minimum
cardinality of a dominating set is the domination number, γ(G), of G. Domination is well
studied in the literature. A recent book on domination in graphs can be found in [10]. A
small sample of papers on domination critical graphs can be found in [3, 4, 5, 6, 9, 17, 18].
Adopting the notation coined by Bauer et al. [3], the γ−-stability (γ+-stability, resp.) of
G, denoted by γ−(G) (γ+(G), resp.), is the minimum number of vertices whose removal
decreases (increases, resp.) the domination number. The minimum number of vertices
whose removal decreases or increases the domination number is the domination stability,
stγ(G), of G, and so stγ(G) = min{γ−(G), γ+(G)}.
We refer to a graph without isolated vertices as an isolate-free graph. Unless otherwise
stated, let G be an isolate-free graph. A total dominating set, abbreviated TD-set, of G
is a set D of vertices of G such that every vertex, including vertices in the set D, has
a neighbor in D. The minimum cardinality of a TD-set of G is the total domination number,
γt(G), of G. We call a TD-set of G of cardinality γt(G) a γt-set of G. A vertex v is totally
dominated by a set D in G if the vertex v has a neighbor in D. We refer the reader to
the book [14] for fundamental concepts on total domination in graphs. Total domination
critical graphs are studied, for example, in [7, 13]. The total version of domination stability
was first studied by Henning and Krzywkowski [12].
A paired dominating set, abbreviated PD-set, of an isolate-free graph G is a dominating
set S of G with the additional property that the subgraph G[S] induced by S contains
a perfect matching M (not necessarily induced). With respect to the matching M , two
vertices joined by an edge of M are paired and are called partners in S. The paired
domination number, γpr(G), of G is the minimum cardinality of a PD-set of G. We call
a PD-set of G of cardinality γpr(G) a γpr-set of G. We note that the paired domination
number γpr(G) is an even integer. For a recent survey on paired domination in graphs, we
refer the reader to the book chapter [8].
Every PD-set is a TD-set, implying that γt(G) ≤ γpr(G). A non-isolating set of ver-
tices in G is a set S ⊆ V such that the graph G − S is isolate-free, where G − S is the
graph obtained from G by removing S and all edges incident with vertices in S. Let NI(G)
denote the set of all non-isolating sets of vertices of G.
Adopting the standard notation for domination stability given in [3, 12], the γ−pr-stability
E-mail addresses: agorzkow@agh.edu.pl (Aleksandra Gorzkowska), mahenning@uj.ac.za (Michael A.
Henning), pilsniak@agh.edu.pl (Monika Pilśniak), etumid@agh.edu.pl (Elżbieta Tumidajewicz)
A. Gorzkowska et al.: Paired domination stability in graphs 233
(resp., γ+pr-stability) of G, denoted by st
−
γpr(G) (resp., st
+
γpr(G)) is the minimum cardinality
of a set in NI(G) whose removal decreases (increases, resp.) the paired domination number.
Thus,
st−γpr(G) = minS∈NI(G)
{ |S| : γpr(G− S) < γpr(G)}
and
st+γpr(G) = minS∈NI(G)
{ |S| : γpr(G− S) > γpr(G)}.
If there is no set in NI(G) whose removal increases the paired domination number,
then we define st+γpr(G) = ∞. For example, st
−
γpr(P5) = 1 while st
+
γpr(P5) = ∞.
The paired domination stability, stγpr(G), of G is the minimum cardinality of a set in
NI(G) whose removal increases or decreases the paired domination number. Thus,
stγpr(G) = min
S∈NI(G)
{ |S| : γpr(G− S) ̸= γpr(G)} = min{st−γpr(G), st
+
γpr(G)}.
Let G be a graph and let S ∈ NI(G). If γpr(G − S) < γpr(G) and |S| = st−γpr(G), then
we call S a st−γpr -set of G. If γpr(G − S) > γpr(G) and |S| = st
+
γpr(G), then we call S
a st+γpr -set of G. If γpr(G − S) ̸= γpr(G) and |S| = stγpr(G), then we call S a stγpr -set
of G.
Defining the null graph K0, which has no vertices, as a graph, we have the following
results due to Bauer et al. [3] and Rad et al. [15] for the γ−-stability of a graph.
Theorem 1.1 ([3, 15]). If G is an isolate-free graph of order n, then the following holds.
(a) stγ(G) ≤ δ(G) + 1.
(b) If G ≇ Kn, then stγ(G) ≤ n− 1.
Considering the null graph, the paired domination stability of a non-trivial graph is
always defined. If G is a graph of order n and γpr(G) = 2, then st−γpr(G) = n since
removing all vertices from the graph G produces the null graph with paired domination
number zero.
For notation and graph theory terminology we generally follow [14]. In particular, for
r, s ≥ 1, a double star S(r, s) is the tree with exactly two vertices that are not leaves, one
of which has r leaf-neighbors and the other s leaf-neighbors. A rooted tree is a tree T in
which we specify one vertex r called the root. For each vertex v of T different from r,
its parent is the neighbor of v on the unique (r, v)-path, while every other neighbor of v
is a child of v in T . If w is a vertex of T different from v and the (unique) (r, w)-path
contains v, then w is a descendant of v in T . We note that every child of v is a descendant
of v. The diameter diam(G) of G is the maximum distance among all pairs of vertices of
G. A diametral path in G is a shortest path between two vertices in G of length equal to
diam(G). For an integer k ≥ 1, [k] = {1, . . . , k}.
2 Main results
Our first aim is to show that the paired domination stability of a graph can be very different
from its total domination stability studied in [12].
Theorem 2.1. For k ≥ 1 an arbitrary integer, the following holds.
234 Ars Math. Contemp. 22 (2022) #P2.04 / 231–248
(a) There exist connected graphs G such that st−γpr(G)− st
−
γt(G) = k.
(b) There exist connected graphs H such that st−γt(H)− st
−
γpr(H) = k.
Our second aim is to establish properties of paired domination stability in graphs.
Thereafter, we establish upper bounds on the paired domination stability and the γ−pr-
stability of a graph. For this purpose, we shall need the following family of trees defined by
Henning and Krzywkowski [12]. For integers k ≥ 2 and ∆ ≥ 2, the authors in [12] define
Tk,∆ as the “graph obtained from the disjoint union of k double stars S(∆− 1,∆− 1) by
adding k − 1 edges between the leaves of these double stars so that the resulting graph is
a tree with maximum degree ∆." Let Fk,∆ be the family of all such trees Tk,∆, and let
F∆ =
⋃
k≥2
Fk,∆.
The following result establishes an upper bound on the γ−pr-stability of a tree, and char-
acterizes the trees with maximum possible γ−pr-stability.
Theorem 2.2. If T is a tree with maximum degree ∆ satisfying γpr(T ) ≥ 4, then the
following hold.
(a) st−γpr(T ) ≤ 2∆, with equality if and only if T ∈ F∆.
(b) stγpr(T ) ≤ 2∆− 1, and this bound is sharp for all ∆ ≥ 2.
For general graphs, we establish the following upper bound on the γ−pr-stability in terms
of the maximum degree of the graph.
Theorem 2.3. If G is a connected graph with γpr(G) ≥ 4, then st−γpr(G) ≤ 2∆(G), and
this bound is sharp.
As an immediate consequence of Theorem 2.3, we have the following upper bound on
the paired domination stability of a graph.
Corollary 2.4. If G is a connected graph with γpr(G) ≥ 4, then stγpr(G) ≤ 2∆(G).
3 Paired stability versus domination and total stability
In this section, we show that paired domination stability and the domination stability of
a graph can be very different. By Theorem 1.1, for every nontrivial graph G, we have
stγ(G) ≤ δ(G) + 1. In particular, stγ(T ) ≤ 2 for every nontrivial tree T . This is in
contrast to the paired domination stability, where for any given ∆ ≥ 2, we show that there
exist a family of trees T with maximum degree ∆ satisfying stγpr(T ) = 2∆− 1.
For ∆ = 2, the authors in [12] define H∆ as the family of all paths of order at least 7
and congruent to 3 modulo 4, that is, H∆ = {Pn | n ≡ 3 (mod 4) and n ≥ 7}. For
integers ∆ ≥ 3 and ∆ ≥ k ≥ 2, they define Hk,∆ as the graph “obtained from the disjoint
union of k double stars S(∆ − 1,∆ − 1) by selecting one leaf from each double star and
identifying these k leaves into one new vertex" and they define the family
H∆ =
⋃
k≥2
Hk,∆.
We determine next the paired domination stability of a tree in the family H∆.
A. Gorzkowska et al.: Paired domination stability in graphs 235
Proposition 3.1. For ∆ ≥ 3, if T ∈ H∆, then stγpr(T ) = 2∆− 1.
Proof. For integers ∆ ≥ k ≥ 2 where ∆ ≥ 3, consider a tree T ∈ Hk,∆. By definition
of the family Hk,∆, the tree T is constructed from the disjoint union of k double stars
S1, . . . , Sk, each isomorphic to S(∆ − 1,∆ − 1), by selecting one leaf from each double
star and identifying these k chosen leaves into one new vertex, which we call vc. Let xi
and yi be the two central vertices of the double star Si for i ∈ [k], where xi is adjacent to
vc in T . Let D = ∪ki=1{xi, yi}. Since ∆ ≥ 3, every vertex in D is a support vertex of
T , implying that every PD-set in T contains the set D and therefore γpr(T ) ≥ |D| = 2k.
Since the set D is a PD-set of T (with the vertices xi and yi paired for all i ∈ [k]), we have
γpr(T ) ≤ |D| = 2k. Consequently, γpr(T ) = 2k and D is the unique γpr-set of T .
Let S be a stγpr -set of T . Thus, S is a set in NI(T ) with |S| = stγpr(T ) satisfying
γpr(T − S) ̸= γpr(T ) = 2k. We show that |S| ≥ 2∆ − 1. Suppose, to the contrary, that
|S| ≤ 2∆− 2. If the set S contains both xi and yi for some i ∈ [k], then since S is a non-
isolating set of T every leaf neighbor of xi and yi is also in S, implying that |S| ≥ 2∆− 1,
a contradiction. Hence, the set S contains at most one of xi and yi for every i ∈ [k]. Let
D∗ be a γpr-set of T − S, and so |D∗| ≠ 2k.
Suppose that vc ∈ S. In this case, if |S| = 1, then the paired domination numbers of
T and T − S are the same, a contradiction. Hence, |S| ≥ 2. If neither xi nor yi belong
to S for some i ∈ [k], then by the minimality of the non-isolating set S, no vertex of Ti
different from vc belongs to S, and so |D∗ ∩ V (Ti)| = 2. If S contains yi but not xi for
some i ∈ [k], then every leaf neighbor of yi is in S and by the minimality of the set S, no
leaf neighbor of xi belongs to S, and so |D∗ ∩ V (Ti)| = 2. Analogously, if S contains xi
but not yi for some i ∈ [k], then |D∗ ∩ V (Ti)| = 2. This is true for all i ∈ [k], implying
that |D∗| =
∑k
i=1 |D∗ ∩ V (Ti)| = 2k, a contradiction. Hence, vc /∈ S.
As observed earlier, the set S contains at most one of xi and yi for every i ∈ [k]. If
yi ∈ S and yj ∈ S for some i, j ∈ [k] where i ̸= j, then |S| ≥ 2∆, a contradiction. If
yi ∈ S and xj ∈ S for some i, j ∈ [k] where i ̸= j, then |S| ≥ 2∆ − 1, a contradiction.
If xi ∈ S and xj ∈ S for some i, j ∈ [k] where i ̸= j, then |S| ≥ 2∆− 2. In this case, by
the minimality of S we have S = (N [xi] ∪ N [xj ]) \ {vc, yi, yj} and |S| = 2∆ − 2. But
then T − S consists of three components, namely two stars isomorphic to K1,∆−1 and one
component belonging to the family T ∈ Hk−2,∆ with paired domination number 2(k− 2).
Thus, γpr(T − S) = 2+ 2+ 2(k− 2) = 2k, a contradiction. Therefore, stγpr(T ) = |S| ≥
2∆− 1, as claimed.
Conversely, if we take S = N(x1) ∪ N(y1) \ {vc}, then S ∈ NI(T ) and T − S ∈
Hk−1,∆. Thus, γpr(T − S) = 2(k − 1) < γpr(T ), and so stγpr(T ) ≤ st−γpr(T ) ≤ |S| =
2∆− 1. Consequently, stγpr(T ) = st−γpr(T ) = 2∆− 1.
As observed earlier, stγ(T ) ≤ 2 for every nontrivial tree T . By Proposition 3.1, paired
domination stability therefore differs significantly from domination stability. We show next
that the paired domination stability and the total domination stability of a graph can also be
very different.
Proposition 3.2. For k ≥ 1 an integer, there exist trees T such that st−γpr(T )−st
−
γt(T ) = k.
Proof. Let k ≥ 1 be a given integer, and let T = Tk be obtained from a path P5 given
by v1v2v3v4v5 by attaching k leaf neighbors to each of v1, v2 and v3 (see Figure 1). We
236 Ars Math. Contemp. 22 (2022) #P2.04 / 231–248
note that {v1, v2, v3, v4} is the unique γt-set of T and the unique γpr-set of T . In partic-
ular, γt(T ) = γpr(T ) = 4. If S = {v5}, then the set S is a non-isolating set of T and
γt(T − S) = |{v1, v2, v3}| = 3 < γt(T ), implying that st−γt(T ) = 1.
We show next that st−γpr(T ) = k + 1. Let S be a non-isolating set of T such that
γpr(T − S) < γpr(T ). We show that |S| ≥ k + 1. Suppose, to the contrary, that |S| ≤ k.
Let D be a γpr-set of T − S, and so |D| = γpr(T − S) = 2. Let Li denote the set of leaf
neighbors of vi for i ∈ [4]. If vi ∈ S for some i ∈ [3], then S contains all k leaf neighbors
of vi, and so |S| ≥ k + 1, a contradiction. Hence, S ∩ {v1, v2, v3} = ∅. If {v1, v3} ⊂ D,
then |D| ≥ 4, a contradiction. If v1 /∈ D, then L1 ⊆ S, implying that S = L1 and
|S| = k. However in this case, {v2, v3, v4} ⊂ D. If v3 /∈ D, then L3 ⊆ S, implying that
S = L3 and |S| = k. However in this case, {v1, v2, v4} ⊂ D. In both cases, |D| ≥ 4,
a contradiction. Therefore, |S| ≥ k + 1, implying that st−γpr(T ) ≥ k + 1. Conversely, if
S = L1 ∪ L4, then S is a non-isolating set of T such that γpr(T − S) = |{v2, v3}| <
γpr(T ), implying that st−γpr(T ) ≤ |S| = k + 1. Consequently, st
−
γpr(T ) = k + 1. Thus,
st−γpr(T )− st
−
γt(T ) = k.
   

v1 v2 v3 v4
v5

  . . .
k

  . . .
k

  . . .
k
Figure 1: A tree from the family Tk in the proof of Proposition 3.2.
Proposition 3.3. For k ≥ 1 an integer, there exist trees T such that st−γt(T )−st
−
γpr(T ) = k.
Proof. Let k ≥ 1 be a given integer, and let ℓ ≥ 2k + 1 be an integer. For i ∈ [k], let
Qi be obtained from a path vi1vi2vi3vi4vi5 by attaching ℓ leaf neighbors to each of vi3 , vi4
and vi5 , and let Li3 , Li4 and Li5 be the resulting sets of leaf neighbors of vi3 , vi4 and vi5 ,
respectively. Let Q be obtained from a path v1v2v3 by attaching ℓ leaf neighbors to each of
v1 and v2, and attaching k leaf neighbors to v3. Let Li be the resulting set of leaf neighbors
of vi for i ∈ [3]. Let T be obtained from the disjoint union of the paths Q,Q1, . . . , Qk
by adding the k edges v3vi1 for i ∈ [k]. Let A be the set of support vertices of T , and so
|A| = 3(k + 1).
Every TD-set of T contains all its support vertices, implying that γt(T ) ≥ |A|. Since
the set A is a TD-set of T , we have γt(T ) ≤ |A|. Consequently, γt(T ) = |A| = 3(k + 1).
Every PD-set of T contains the set A and at least one additional vertex from each path
Qi that is a neighbor of vi3 or vi5 for i ∈ [k], and at least one additional vertex that is
a neighbor of v1 or v3 since the vertices of every PD-set are paired, implying that γpr(T ) =
|A|+ k + 1 = 4(k + 1).
Let S be a non-isolating set of T such that γpr(T −S) < γpr(T ). If |S| < k, then every
support vertex of T remains a support vertex of T −S, implying that γpr(T −S) ≥ γpr(T ),
a contradiction. Hence, |S| ≥ k. Conversely, if S∗ = L3, then the set A\{v3} of all support
vertices of T − S∗, together with the vertices vi2 for i ∈ [k], form a PD-set of T − S∗,
implying that γpr(T − S∗) ≤ 4k + 2 < 4k + 4 = γpr(T ). Hence, st−γpr(T ) ≤ |S
∗| = k.
Consequently, st−γpr(T ) = k.
A. Gorzkowska et al.: Paired domination stability in graphs 237
We show next that st−γt(T ) = 2k. Let A
′ = A \ {v3}, and so |A′| = |A| − 1 =
3k + 2. Let S be a non-isolating set of T such that γt(T − S) < γt(T ). We show that
|S| ≥ 2k. Suppose, to the contrary, that |S| ≤ 2k − 1. Let D be a γt-set of T − S, and
so |D| = γt(T − S) ≤ 3k + 2. Since |S| < 2k < ℓ and each vertex in A′ has ℓ leaf
neighbors in T , we note that every vertex of A′ is a support vertex of T − S, implying that
A′ ⊆ D, and so 3k + 2 ≥ |D| ≥ |A′| = 3k + 2, implying that D = A′. In particular,
v3 /∈ D, implying that all k leaf neighbors of v3 belong to S; that is, L3 ⊆ S. If vi1 /∈ S
for some i ∈ [k], then in order to totally dominate the vertex vi1 , the vertex vi2 ∈ D,
contradicting our earlier observation that D = A′. Hence, vi1 ∈ S for all i ∈ [k], and so
|S| ≥ |L3|+k = 2k, a contradiction. Therefore, our original supposition that |S| ≤ 2k−1
is incorrect, implying that |S| ≥ 2k and st−γpr(T ) ≥ 2k. Conversely, if S
∗ consists of
all 2k neighbors of v3 different from v2 in T , then S∗ is a non-isolating set of T such
that γt(T − S∗) = |A′| < γt(T ), implying that st−γt(T ) ≤ |S
∗| = 2k. Consequently,
st−γt(T ) = 2k. Thus, st
−
γt(T )− st
−
γpr(T ) = k.
  v1 v2 v3


...k
 
. . .
l

 
. . .
l

 
. . .
k
   
 
. . .
l

 
. . .
l

 
. . .
l
   
 
. . .
l

 
. . .
l

 
. . .
l
Figure 2: A tree from the family T in the proof of Proposition 3.3.
Theorem 2.1 follows from Propositions 3.2 and 3.3. As further examples, we remark
that if P is the Petersen graph, then γt(P ) = 4 and γpr(P ) = 6. Further, if v is an arbitrary
vertex of P , then γt(P − v) = 4, and so st−γt(P ) ≥ 2. Moreover, if S consists of two
non-adjacent vertices of P , then γt(P − S) = 3, and so st−γt(P ) ≤ 2. Consequently,
st−γt(P ) = 2. However if v is an arbitrary vertex of P , then γpr(P − v) = 4, implying that
st−γpr(P ) = 1. Moreover, let Gk be a graph obtained from the Petersen graph by replacing
every vertex by a copy of a complete graph Kk for some k ≥ 1, and adding all edges
between two resulting complete graphs that correspond to two vertices of Gk (see Fig. 3).
The resulting graph Gk is a (4k−1)-regular, 3k-connected graph that satisfies γt(Gk) = 4
and st−γt(Gk) = 2k, and γpr(Gk) = 6 and st
−
γpr(Gk) = k. This yields the following result.
Proposition 3.4. For k ≥ 1 an integer, there exists (4k− 1)-regular, 3k-connected graphs
G such that st−γt(G)− st
−
γpr(G) = k.
4 Properties of paired domination stability
In this section, we present properties of paired domination stability in graphs. We begin
with the following property of paired domination in graphs.
238 Ars Math. Contemp. 22 (2022) #P2.04 / 231–248
Kk Kk
KkKk
Kk
Kk Kk
KkKk
Kk
Figure 3: A graph Gk obtained from the Petersen graph by replacing every vertex by Kk.
Proposition 4.1. Every connected isolate-free graph G contains a spanning tree T such
that γpr(T ) = γpr(G).
Proof. Since adding edges to a graph cannot increases its paired domination number, if
T is an isolate-free spanning subgraph of a graph G, then γpr(G) ≤ γpr(T ). Let D be
a γpr-set of G, and so D is a PD-set of G and |D| = γpr(G). Let M be a perfect matching
in the subgraph G[D] induced by D. Let T ′ be a spanning subgraph of G that consists
of the edges in M and for each vertex v outside D, an edge of G that joins v to exactly
one vertex of the dominating set D. If the resulting spanning subgraph T ′ is a tree, then
we let T = T ′. Otherwise, if the resulting spanning subgraph T ′ is a forest with ℓ ≥ 2
components, then we add ℓ − 1 edges from the edge set of the graph G between these
components, avoiding cycles, to construct a tree, which we call T . Since D is a PD-set
in the resulting tree T , we note that γpr(T ) ≤ |D| = γpr(G). Since T is an isolate-free
spanning subgraph of G, we have γpr(T ) ≥ γpr(G). Consequently, T is a spanning tree of
G satisfying γpr(T ) = γpr(G).
By our earlier convention, if G is a graph of order n and γpr(G) = 2, then st−γpr(G) = n
since removing all vertices from the graph G produces the null graph with paired domi-
nation number zero. We are therefore only interested in the γ−pr-stability of graphs with
paired domination number at least 4. If G is a graph with γpr(G) ≥ 4 where x and
y are adjacent vertices in G, then D = V (G) \ {x, y} belongs to the set NI(G) and
γpr(G−D) = γpr(K2) = 2 < γpr(G). This yields the following result.
Observation 4.2. Every isolate-free graph G of order n with γpr(G) ≥ 4 satisfies
st−γpr(G) ≤ n− 2.
Proposition 4.3. If T is a spanning tree of a connected graph G such that
γpr(T ) = γpr(G), then st−γpr(T ) ≥ st
−
γpr(G).
Proof. Let S be a st−γpr -set of T . Thus, S is a set in NI(T ) with |S| = st
−
γpr(T ) such
that γpr(T − S) < γpr(T ). Since γpr(G − S) ≤ γpr(T − S) and γpr(T ) = γpr(G),
the set S is a non-isolating set of G such that γpr(G − S) < γpr(G). Hence, st−γpr(G) ≤
|S| = st−γpr(T ).
The following result shows that to determine the γ−pr-stability of a graph G, it is not
sufficient to only examine spanning trees T of G satisfying γpr(T ) = γpr(G).
A. Gorzkowska et al.: Paired domination stability in graphs 239
Proposition 4.4. For k ≥ 1 an integer, there exist connected graphs G such that
st−γpr(T )− st
−
γpr(G) = k for every spanning tree T of G with γpr(T ) = γpr(G).
Proof. For k ≥ 1, let F be obtained from two vertex disjoint copies of K2,k+1 by iden-
tifying a vertex of degree k + 1 from each copy. Let u be the resulting identified vertex
of degree 2(k + 1), and let w1 and w2 be the two vertices of degree k + 1 in F . Fur-
ther, let vi be a common neighbor (of degree 2) of u and wi for i ∈ [2]. Let G be ob-
tained from F by adding a leaf neighbor xi to wi for i ∈ [2]. Thus, diam(G) = 6 and
x1w1v1uv2w2x2 is a shortest path in G of length 6. The graph G satisfies γpr(G) = 4.
We remark that only connected graphs of diam(G) ≤ 3 have γpr(G) = 2. Therefore,
st−γpr(G) ≥ 3. Moreover, the set S = {w1, x1, x2} is a non-isolating set of minimum car-
dinality satisfying γpr(G − S) = 2 < γpr(G), and so st−γpr(G) = 3. However, the vertex
u must have degree 2 in every spanning tree T of G for which γpr(T ) = γpr(G) = 4,
implying that the vertices w1 and w2 each have k + 1 leaf neighbors in T . This implies
that every non-isolating set of T that decreases the paired domination number contains at
least k + 3 vertices. The set S = NT [w1] is a non-isolating set of minimum cardinality
satisfying γpr(T − S) = 2 < γpr(T ), and so st−γpr(T ) ≤ |S| = k + 3. Consequently,
st−γpr(T ) = k + 3, and so st
−
γpr(T )− st
−
γpr(G) = k.
Proposition 4.5. If S is a st−γpr -set of a connected isolate-free graph G with γpr(G) ≥ 4,
then γpr(G− S) = γpr(G)− 2.
Proof. Let S be a st−γpr -set of G. Suppose, to the contrary, that γpr(G− S) ≤ γpr(G)− 4.
By the connectivity of G, there exists a vertex u ∈ S that has a neighbor in the set V (G)\S.
We now consider the set S′ = S\{u}. Let D be a γpr-set of G−S. If u has a neighbor in D,
then D is a γpr-set of G−S′, implying that γpr(G−S′) ≤ |D| = γpr(G−S) ≤ γpr(G)−4,
contradicting our choice of the set S. Hence, u has no neighbor in D. Let v be an arbitrary
neighbor of u that belongs to V (G) \ S. The set D ∪ {u, v} is a PD-set of G − S′ with u
and v paired, and with the pairings of the vertices of D unchanged from their pairings in
G−S. Hence, γpr(G−S′) ≤ |D|+2 ≤ γpr(G)− 2, once again contradicting our choice
of the set S.
5 Paths and cycles
It is well known (see, for example, [11]) that for n ≥ 3 we have γpr(Cn) = γpr(Pn) =
2⌈n4 ⌉. In this section, we determine the paired domination stability of paths and cycles.
The proofs require a detailed case analysis, which is straightforward albeit tedious. We
therefore omit the proofs in this section. The γ−pr-stability of a path Pn and a cycle Cn on
n vertices is given by the following result.
Theorem 5.1. If G is a path Pn, for n ≥ 2, or a cycle Cn, for n ≥ 3, then
st−γpr(G) =

1 when n ≡ 1 (mod 4)
2 when n ≡ 2 (mod 4)
3 when n ≡ 3 (mod 4)
4 when n ≡ 0 (mod 4).
Next we determine the γ+pr-stability of a path Pn. For n ≤ 10 with n ̸= 8 and for
n = 13, no non-isolating set of vertices in a path Pn exists whose removal increases the
240 Ars Math. Contemp. 22 (2022) #P2.04 / 231–248
paired domination number, and hence, by definition, st+γpr(Pn) = ∞ for such values of n.
It is therefore only of interest to determine the γ+pr-stability of a path Pn, where n ≥ 8 and
n /∈ {9, 10, 13}.
Theorem 5.2. For n ≥ 8 and n /∈ {9, 10, 13},
st+γpr(Pn) =
{
1 when n (mod 4) ∈ {0, 3}
2 when n (mod 4) ∈ {1, 2}.
As a consequence of Theorems 5.1 and 5.2, the paired domination stability of a path is
determined.
Corollary 5.3. For n ≥ 2,
stγpr(Pn) =

1 when n (mod 4) ∈ {0, 1, 3} and n /∈ {3, 4, 7}
2 when n ≡ 2 (mod 4)
3 when n ∈ {3, 7}
4 when n = 4.
We next consider the γ+pr-stability of a cycle Cn. As shown in Theorem 5.1, the γ
−
pr-
stability of a path and a cycle of the same order are equal. This is not always the case for
the γ+pr-stability of a path and a cycle. For example, st
+
γpr(P12) = 1 and st
+
γpr(C12) = 2.
Analogously as in the case of paths, for small values of the order of a cycle the γ+pr-stability
is infinite. Namely, for n ≤ 14 with n ̸= 12 and n = 17 we have that st+γpr(Cn) = ∞. The
following result determines the γ+pr-stability of a cycle of large order.
Theorem 5.4. For n ≥ 12 and n /∈ {13, 14, 17},
st+γpr(Cn) =

2 when n ≡ 0 (mod 4)
3 when n (mod 4) ∈ {2, 3}
4 when n ≡ 1 (mod 4).
As a consequence of Theorems 5.1 and 5.4, the paired domination stability of a cycle
is determined.
Corollary 5.5. For n ≥ 3,
stγpr(Cn) =

1 when n ≡ 1 (mod 4)
2 when n (mod 4) ∈ {0, 2} and n /∈ {4, 8}
3 when n ≡ 3 (mod 4)
4 when n ∈ {4, 8}.
6 Trees
In this section, we first determine the γpr-stability of trees in the family F∆ and a new
family E∆.
Lemma 6.1. For ∆ ≥ 2, if T ∈ F∆, then st−γpr(T ) = 2∆.
A. Gorzkowska et al.: Paired domination stability in graphs 241
Proof of Lemma 6.1. Let T be an arbitrary tree in the family Fk,∆ for some k ≥ 2 and
∆ ≥ 2. We show that st−γpr(T ) = 2∆. The family Fk,2 consists of all paths P4k where
k ≥ 2. Therefore by Theorem 5.1, we have st−γpr(T ) = 4 = 2∆ for each T ∈ Fk,2, which
yields the desired result. Hence, we may assume that ∆ ≥ 3. We show, by induction on
k ≥ 2, that every tree T in the family Fk,∆ satisfies st−γpr(T ) = 2∆.
Suppose k = 2, and so T ∈ F2,∆ (where recall that ∆ ≥ 3). The tree T can therefore
be constructed from two vertex disjoint double stars T1 and T2, where Ti ∼= S(∆−1,∆−1)
for i ∈ [2], by selecting leaves w1 and w2 of T1 and T2, respectively, and adding the edge
w1w2 to T1 ∪ T2. Let xi and yi be the two vertices of Ti that are not leaves, where xiwi is
an edge. We note that y1x1w1w2x2y2 is a path in T . We note that γpr(T ) = 4 and the set
{x1, x2, y1, y2} is a γpr-set of T .
Let S be a st−γpr -set of G. Thus, S is a set in NI(G) with |S| = st
−
γpr(G) such that
γpr(T − S) = 2. Let R be a γpr-set of T − S, and so R is a minimum PD-set of
T − S (of cardinality 2). Since T [R] = P2, we note that T − S is a tree of diameter
at most 3. This implies that at most one of xi and y3−i belong to T − S for i ∈ [2]. Thus,
|S ∩ {xi, y3−i}| ≥ 1 for i ∈ [2].
Suppose that y1 ∈ S and x2 ∈ S. If x1 ∈ S, then all leaf neighbors of y1, x1 and x2
belong to S, while if y2 ∈ S, then all leaf neighbors of y1, y2 and x2 belong to S. In both
cases, |S| ≥ 3∆− 2 > 2∆.
Suppose that y1 ∈ S and x2 /∈ S. If y2 ∈ S, then all leaf neighbors of y1 and y2
belong to S, implying that |S| ≥ 2∆. If y2 /∈ S, then x1 ∈ S, implying that S contains all
leaf-neighbors of y1 and x1, and so |S| ≥ 2∆− 1. However if in this case |S| = 2∆− 1,
implying that diam(T − S) ≥ 4, a contradiction. Hence, |S| ≥ 2∆.
Suppose that y1 /∈ S and x2 ∈ S. Since T − S is a tree, y2 ∈ S and all leaf neighbors
of y2 and x2 belong to S, implying that |S| ≥ 2∆ − 1. However if in this case |S| =
2∆− 1, then S contains x2 and all leaf neighbors of y1, implying that diam(T − S) ≥ 4,
a contradiction. Hence, |S| ≥ 2∆. Therefore, in all three cases we have |S| ≥ 2∆, as
desired. This proves the base case when k = 2.
For the inductive hypothesis, let k ≥ 3 and assume that if T ′ ∈ Fk′,∆ where 2 ≤ k′ <
k, then st−γpr(T
′) = 2∆. We now consider a tree T in the family Fk,∆. Therefore, the
tree T can be constructed from k vertex disjoint double stars H1, . . . ,Hk, where Hi ∼=
S(∆− 1,∆− 1) for i ∈ [k], by selecting one leaf yi from each double star Hi and adding
k−1 edges between vertices in {y1, . . . , yk} in such a way that the resulting graph is a tree
with maximum degree ∆. Let wi and xi be the two (adjacent) vertices of Hi that are not
leaves for i ∈ [k], where yi is a leaf neighbor of xi for i ∈ [k]. We note that γpr(T ) = 2k
and the set ∪ki=1{wi, xi} is the unique γpr-set of T .
Let U be the graph of order k whose vertices correspond to the k double stars
H1, . . . ,Hk where two vertices are adjacent in U if and only if the corresponding dou-
ble stars are joined by an edge in T . We call U the underlying graph of T . By construction,
the graph U is a tree, noting that T is a tree. Let V (U) = {u1, . . . , uk} where ui is the
vertex of U corresponding to the double star Hi for i ∈ [k]. Renaming the double stars if
necessary, we may assume that u1 is a leaf in U , and that H1 is joined to H2 in T . Thus,
y1y2 ∈ E(T ) and y1yj /∈ E(T ) for j ∈ [k] \ [2]. We note that w1x1y1y2x2w2 is a path
in T . Let T ′ = T −V (H1). By construction, the tree T ′ belongs to the family Fk′,∆ where
k′ = k − 1 ≥ 2. By induction, we have st−γpr(T
′) = 2∆.
Let S be a st−γpr -set of T . Thus, S is a set in NI(T ) with |S| = st
−
γpr(T ) such that
γpr(T − S) ≤ γpr(T ) − 2 = 2k − 2. Let Q be a γpr-set of T − S, and so |Q| ≤ 2k − 2.
242 Ars Math. Contemp. 22 (2022) #P2.04 / 231–248
Let Q′ = Q ∩ V (T ′) and S′ = S ∩ V (T ′). For i ∈ [k], let Qi = Q ∩ V (Hi) and
Si = S ∩ V (Hi). We proceed further with the following claim.
Claim 6.2. |S| ≥ 2∆.
Proof of Claim 6.2. Suppose, to the contrary, that |S| ≤ 2∆− 1.
Subclaim 6.2.1. |Q1| ≥ 2.
Proof of Subclaim 6.2.1. Suppose, to the contrary, that |Q1| ≤ 1. Suppose that Q1 = ∅.
In this case, V (H1) \ {y1} ⊆ S1. If y1 ∈ S1, then |S1| = 2∆ > |S|, a contradiction.
Hence, y1 /∈ S1, and so 2∆ − 1 ≥ |S| ≥ |S1| = 2∆ − 1, implying that S = S1 and
|S| = 2∆− 1. In this case, a γpr-set of T − S contains at least one of y1 and y2. Since the
set ∪ki=2{wi, xi} is the unique γpr-set of T ′, a γpr-set of T − S is therefore not a γpr-set
of T ′, and so γpr(T − S) ≥ γpr(T ′) + 2 = 2(k − 1) + 2 = 2k, a contradiction. Hence,
|Q1| ≥ 1.
By supposition, |Q1| ≤ 1. Consequently, |Q1| = 1, implying that Q1 = {y1} and
V (H1) \ {x1, y1} ⊆ S1, and so |S1| ≥ 2∆ − 2. If x1 ∈ S1, then |S1| = 2∆ − 1
and we end up in the previous case, which leads to a contradiction. Hence, x1 /∈ S1 and
x1 /∈ Q1, implying that y2 ∈ Q with the vertices y1 and y2 paired in Q, and |S1| = 2∆−2.
By supposition, |S| ≤ 2∆ − 1. If |S| = 2∆ − 2, then S = S1 and γpr(T − S) ≥
γpr(T
′)+2 = 2k, a contradiction. Hence, |S| = 2∆−1, and so the set S contains a vertex
v′ ∈ V (T ′)\{y2}. However noting that ∆ ≥ 3, every non-isolating set of vertices of T ′−y2
that decreases the paired domination number cannot contain only one vertex, implying that
γpr(T − S) ≥ |{y1, y2}|+ γpr(T ′ − y2) = 2 + γpr(T ′) = 2k, a contradiction.
Subclaim 6.2.2. {x1, y1} ⊆ Q.
Proof of Subclaim 6.2.2. Suppose, to the contrary, that y1 /∈ Q1, implying that S′ ∈
NI(T ′). Recall that S is a st−γpr -set of T and |S
′| ≤ |S| ≤ 2∆− 1. However, st−γpr(T
′) =
2∆. Therefore, γpr(T ′−S′) ≥ γpr(T ′) = 2(k−1). Hence, γpr(T −S) = γpr(T ′−S′)+
|Q1| ≥ 2(k − 1) + 2 = 2k, a contradiction. Hence, y1 ∈ Q1.
Suppose, to the contrary, that x1 /∈ Q1. Thus, all ∆ − 2 leaf-neighbors of x1 belong
to the set S1. By Claim 6.2.1, we have |Q1| ≥ 2. Hence, the set Q1 contains w1 and one
of its leaf-neighbor w′1. We now consider the set S
∗ = S \ S1. Since S∗ ∈ NI(T ) and
(Q \ {w′1}) ∪ {x1} is a PD-set of T − S∗, we have γpr(T − S∗) ≤ |Q| = γpr(T − S),
contradicting our choice of the set S. Hence, x1 ∈ Q1.
Subclaim 6.2.3. w1 /∈ Q1.
Proof of Subclaim 6.2.3. Suppose, to the contrary, that w1 ∈ Q1. Hence, {w1, x1, y1} ⊆
Q1, and so S ∩ V (H1) = ∅ by the minimality of S. Thus, S = S′ and therefore
|S′| ≤ 2∆− 1.
We show firstly that x1 and y1 are paired in Q. Suppose, to the contrary, that x1 and
y1 are not paired in Q. This implies that y2 ∈ Q, and that y1 and y2 are paired in Q.
Suppose that x2 /∈ S, implying that S′ ∈ NI(T ′). By the minimality of the set Q, we have
x2 /∈ Q. Thus, the set Q′ ∪ {x2} is a PD-set of T ′ − S′, and so |Q′|+ 1 = |Q′ ∪ {x2}| ≥
γpr(T
′ − S′) ≥ γpr(T ′) = 2(k − 1). Hence, |Q| = |Q1| + |Q′| ≥ 3 + (2k − 3) = 2k =
γpr(T ), a contradiction. Hence, x2 ∈ S. We now consider the set S∗ = S \ {x2}. We note
that S∗ is a non-isolating set of vertices of T , and the set Q is a PD-set of T − S∗. Thus,
A. Gorzkowska et al.: Paired domination stability in graphs 243
γpr(T − S∗) ≤ |Q| ≤ 2k− 2, which contradicts our choice of the set S. Hence, x1 and y1
are paired in Q.
Since x1 and y1 are paired in Q, the vertex w1 is paired with one of its leaf neighbors,
say w′1. By the minimality of Q we note that Q1 = {w1, w′1, x1, y1}. If x2 ∈ Q, then the
set Q\{w′1, y1} is a PD-set of T −S (with w1 and x1 paired), contradicting the minimality
of Q. Hence, x2 /∈ Q. This in turn implies that y2 /∈ Q. If y2 ∈ S, then once again
we contradict the minimality of Q. Therefore, y2 /∈ S. We remark, though, that possibly
x2 ∈ S. Recall that by our earlier observations, S = S′.
Let S′′ = S\{x2}. Thus, if x2 /∈ S, then S′′ = S, while if x2 ∈ S, then S′′ = S\{x2}.
The set S′′ is a non-isolating set of T ′ such that |S′′| ≤ |S| ≤ 2∆ − 1. As observed
earlier, y2 /∈ Q′ and x2 /∈ Q′. The set Q′ ∪ {y2, x2} is a PD-set of T ′ − S′′, implying
that |Q′| + 2 ≥ γpr(T ′ − S′′) ≥ γpr(T ′) = 2(k − 1). Hence, |Q′| ≥ 2k − 4, and so
|Q| = |Q1|+ |Q′| ≥ 4 + (2k − 4) = 2k, contradicting the fact that |Q| ≤ 2k − 2.
Proof of Claim 6.2, continued: By Claim 6.2.3, w1 /∈ Q1. This implies that Q1 = {x1, y1}.
The set S1 therefore consists of the ∆− 1 leaf neighbors of w1, and so |S1| = ∆− 1. This
is true for every leaf in the tree U . Hence, if ui is a leaf in U for some i ∈ [k], then in the
corresponding double star Hi of T we have Qi = {xi, yi} and |Si| = ∆− 1. Further, the
set Si consists of the ∆− 1 leaf neighbors of wi. In particular, |Q1| = 2 and |S1| = ∆− 1.
Since the underlying tree U of T has order k ≥ 3, there are at least two leaves in U . Thus,
up is a leaf in U for some p ∈ [k] \ {1}, implying that |Qp| = 2 and |Sp| = ∆− 1.
If |Qi| ≥ 2 for all i ∈ [k], then |Q| ≥ 2k, a contradiction. Hence, |Qq| ≤ 1
for some q ∈ [k]. By our earlier observations, uq is not a leaf in the tree U , and so
q /∈ {1, p}. If |Qq| = 0, then {wq, xq} ⊆ Sq , and so |Sq| ≥ 2 (in fact, |Sq| ≥ 2∆ − 1)
and |S| ≥ |S1| + |Sp| + |Sq| ≥ (∆ − 1) + (∆ − 1) + 2 = 2∆, a contradiction. Hence,
|Qq| = 1, implying that Qq = {yq} and wq ∈ Sq , and so |Sq| ≥ 1. Since the paired dom-
inating number is an even integer and |Q| ≤ 2k, there exists r ∈ [k] \ {1, p, q} such that
|Qr| = 1. Therefore, Qr = {yr} and |Sr| ≥ 1. Hence, |S| ≥ |S1|+ |Sp|+ |Sq|+ |Sr| ≥
(∆−1)+(∆−1)+1+1 = 2∆, a contradiction. This completes the proof of Claim 6.2.
Proof of Lemma 6.1, continued: By Claim 6.2, we have |S| ≥ 2∆. By our choice of the set
S, this implies that st−γpr(T ) = |S| ≥ 2∆. Conversely, if we consider the set S = V (H1),
then S ∈ NI(T ) satisfies |S| = 2∆ and γpr(T − S) = γpr(T ′) = 2k − 2 < γpr(T ),
and so st−γpr(T ) ≤ 2∆. Consequently, st
−
γpr(T ) = 2∆. This completes the proof of
Lemma 6.1.
We determine next the γ+pr-stability of a tree in the family F∆.
Lemma 6.3. For ∆ ≥ 2, if T ∈ F∆, then st+γpr(T ) ≤ ∆− 1.
Proof. Let T be an arbitrary tree in the family Fk,∆ for some k ≥ 2 and ∆ ≥ 2. We
use the same notation as in the proof of Lemma 6.1. In particular, γpr(T ) = 2k and
H1 corresponds to a leaf u1 in the underlying tree U of T . Moreover, y1y2 is the edge
joining H1 and H2 in T . Also, wi and xi are the support vertices in the double star Hi
and wixiyi is a path in Hi for i ∈ [k]. Let L be the set of ∆ − 2 leaf neighbors of x1
in T , and let S = L ∪ {x1}. We resulting set S ∈ NI(T ) and the forest T − S has two
components, say F1 and F2 where w1 ∈ V (F1) and y1 ∈ V (F2). Moreover, γpr(T −S) =
γpr(F1) + γpr(F2) = 2 + 2k > γpr(T ). Therefore, st+γpr(T ) ≤ |S| = ∆− 1.
244 Ars Math. Contemp. 22 (2022) #P2.04 / 231–248
Recall that by Proposition 3.1, for ∆ ≥ 3, if T ∈ H∆, then stγpr(T ) = 2∆−1. Further
we remark that st+γpr(T ) = ∞. We next define another family of trees T with maximum
degree ∆ such that st−γpr(T ) = 2∆− 1. For integers ∆ ≥ 3 and ∆− 1 ≥ k ≥ 3, let Ek,∆
be a graph obtained from the path P2 with vertices u and v and the disjoint union of 2k
double stars S(∆ − 1,∆ − 1) by selecting one leaf from each double star and identifying
half of the selected leaves with the vertex v and the other half of the selected leaves with
the vertex u (see Figure 4). Let
E∆ =
⋃
k≥3
Ek,∆.
 
 







 







k
















k
Figure 4: A tree Ek,5 from the family E5.
If T is a tree from the family E∆, then st−γpr(T ) = 2∆−1. Moreover, if T is isomorphic
to the graph Ek,∆, then st+γpr(T ) = k(∆− 1). In contrast to the family H∆, the trees from
the family E∆ have finite γ+pr-stability.
7 Proof of Theorem 2.2
In this section we present a proof of Theorem 2.2, which we restate below.
Theorem 2.2. If T is a tree with maximum degree ∆ satisfying γpr(T ) ≥ 4, then the
following hold.
(a) st−γpr(T ) ≤ 2∆, with equality if and only if T ∈ F∆.
(b) stγpr(T ) ≤ 2∆− 1, and this bound is sharp for all ∆ ≥ 2.
Proof. We first prove the statement given in part (a). Since γpr(T ) ≥ 4, we have ∆ ≥ 2.
If ∆ = 2, then G is a path Pn of order n ≥ 5. In this case, the family Fk,∆ = {Pn : n ≡
0 (mod 4) and n ≥ 8}, and Theorem 5.1 and Lemma 6.1 imply the desired result. Suppose,
therefore, that ∆ ≥ 3. The sufficiency of part (a) follows from Lemma 6.1. To prove
the necessity, let T be a tree with maximum degree ∆ ≥ 3 satisfying γpr(T ) ≥ 4. Let
d = diam(T ), and so d ≥ 4. Let P : v0v1 . . . vd be a diametral path in G. Thus, v0 and vd
are leaves in T and d(v0, vd) = diam(G). We now consider the tree T rooted at the vertex
vd. Let D be a γpr-set of T .
Suppose that there is a child u1 of v2 that is a support vertex in T where u1 ̸= v1. Let
u0 be a leaf neighbor of u1. Since every PD-set of T contains all support vertices, we have
{v1, u1} ⊂ D. Renaming vertices if necessary, we may assume that u0 and u1 are paired
in D. Thus, if S consists of the vertex u1 and all leaf neighbors of u1, then S ∈ NI(T ) and
γpr(T − S) ≤ |D| − 2 = γpr(T ) − 2. Hence, st−γpr(T ) ≤ |S| ≤ ∆ < 2∆ − 1, and the
desired result follows. Assume, therefore, that every child of v2 different from v1 is a leaf.
A. Gorzkowska et al.: Paired domination stability in graphs 245
Suppose that there is a γpr-set, D2,3, of T such that v2 and v3 are paired in D2,3.
Necessarily, v1 ∈ D2,3 and v1 is paired in D2,3 with one of its leaf neighbors. Let S
consist of the vertex v1 and all of its leaf neighbors. Thus, S ∈ NI(T ) and γpr(T − S) ≤
|D2,3| − 2 = γpr(T ) − 2 < γpr(T ), implying that st−γpr(T ) ≤ |S| ≤ ∆ < 2∆ − 1, once
again implying the desired result. Therefore, we may assume that in every γpr-set of T the
vertices v2 and v3 are not paired.
Suppose that there is a γpr-set, D3, of T which contains a neighbor of v3 differ-
ent from v2. In this case, if S consists of the vertex v2 and all its descendants, then
|S| ≤ 2∆ − 1, S ∈ NI(T ) and γpr(T − S) ≤ |D3| − 2 = γpr(T ) − 2 < γpr(T ),
noting that the set D3 \ S is a PD-set of T − S and, by the minimality of D3 we have
|D3 ∩ S| = 2. Thus, st−γpr(T ) ≤ |S| ≤ 2∆− 1, and the desired result follows. Hence, we
may assume that every γpr-set of T contains the vertex v2 but no other vertex in N [v3]. In
particular, N [v3] ∩D = {v2}.
Suppose that dT (v1) < ∆ or dT (v2) < ∆. Thus, dT (v1)+ dT (v2) ≤ 2∆− 1. In order
to dominate the vertex v0, we have v1 ∈ D. By our earlier assumptions, v2 ∈ D and every
child of v2 different from v1 is a leaf. Thus by the minimality of the set D, the vertex v1 is
the only descendant of v2 that belongs to the set D, and the vertices v1 and v2 are paired in
D. Hence, if S = N [v2]∪N [v1], then S ∈ NI(T ) and |S| = dT (v1) + dT (v2) ≤ 2∆− 1.
Further, D \ {v1, v2} is a PD-set of T − S, and so γpr(T − S) ≤ |D| − 2 = γpr(T ) − 2,
implying that st−γpr(T ) ≤ |S| ≤ 2∆−1, yielding the desired result. Hence, we may assume
that dT (v1) = dT (v2) = ∆.
Suppose that dT (v3) ≥ 3, and let u2 be a child of v3 different from v2. If u2 is a leaf,
then v3 belongs to every γpr-set of T , while if u2 is not a leaf, then from the structure
of the rooted tree T the vertex u2 can be chosen to belong to some γpr-set of T . In both
cases, we contradict our earlier assumption that every γpr-set of T contains the vertex v2
but no other vertex in N [v3]. Hence, dT (v3) = 2. We now let S = N [v1] ∪ N [v2], and
so S ∈ NI(T ) and |S| = dT (v1) + dT (v2). By our earlier observations, |S| = 2∆ and
γpr(T − S) = γpr(T )− 2 < γpr(T ), implying that st−γpr(T ) ≤ |S| = 2∆. This proves the
desired upper bound.
We show next that if we have equality in the upper bound in part (a), then T ∈ F∆.
Let st−γpr(T ) = 2∆. By our earlier observations, we have that every child of v2 different
from v1 is a leaf. Further, dT (v1) = dT (v2) = ∆ and dT (v3) = 2. We now re-root the
tree T at the vertex v0, thereby interchanging the roles of v0 and vd. Identical arguments
as before show that every child of vd−2 different from vd−1 is a leaf. Further, dT (vd−1) =
dT (vd−2) = ∆ and dT (vd−3) = 2. In particular, d ≥ 6.
Suppose that d = 6, and so vd−3 = v3. In this case, the tree T is determined
and γpr(T ) = 4. Letting S = (N [v1] ∪ N [v2]) \ {v3}, we have S ∈ NI(T ) and
|S| = dT (v1) + dT (v2) − 1 = 2∆ − 1. Further, γpr(T − S) = 2 < γpr(T ). There-
fore, st−γpr(T ) ≤ |S| = 2∆− 1, a contradiction. Hence, d ≥ 7, and so vd−3 ̸= v3.
We now consider the tree T ′ = T − (N [v1] ∪ N [v2]). If γpr(T ′) = 2, then by our
earlier observations, we have d = 7 and T ′ ∼= S(∆ − 1,∆ − 1) where vd−1 and vd−2
are the two (adjacent) vertices in T ′ that are not leaves. Therefore, T ∈ T2,∆, and so T ∈
T∆. Hence, we may assume that γpr(T ′) ≥ 4, for otherwise the desired characterization
follows. In particular, d ≥ 8. As observed earlier, dT (vd−1) = dT (vd−2) = ∆, implying
that ∆(T ′) = ∆ and st−γpr(T
′) ≤ 2∆.
Let D be a γpr-set of T . Since every PD-set of T contains the set of support vertices,
we note that v1, v2 ∈ D. By the minimality of D, no leaf-neighbor of v1 or v2 belongs to
246 Ars Math. Contemp. 22 (2022) #P2.04 / 231–248
D. If v3 ∈ D, then v4 ∈ D (with v3 and v4 paired in D). However in this case, we can
replace v3 in D with an arbitrary neighbor of v4 that does not belong to D. Hence, we can
choose the γpr-set D of T so that v3 /∈ D. The resulting set D when restricted to V (T ′) is
a PD-set of T ′, implying that γpr(T ′) ≤ |D| − 2 = γpr(T )− 2. Conversely, every PD-set
of T ′ can be extended to a PD-set of T by adding to it the vertices v1 and v2 (with v1 and
v2 paired), and so γpr(T ) ≤ γpr(T ′) + 2. Consequently, γpr(T ) = γpr(T ′) + 2.
Suppose that st−γpr(T
′) < 2∆. Let S′ be a st−γpr -set of T
′. Thus, S is a set in NI(T ′)
with |S′| = st−γpr(T
′) < 2∆ such that γpr(T −S′) < γpr(T ′). If D′ is a γpr-set of T ′−S′,
then D′∪{v1, v2} is a PD-set of T−S, and so γpr(T−S′) ≤ |D′|+2 = γpr(T−S′)+2 <
γpr(T
′) + 2 = γpr(T ). Hence, S′ ∈ NI(T ) and γpr(T − S′) < γpr(T ′), implying that
st−γpr(T ) ≤ |S
′| = st−γpr(T
′) < 2∆, a contradiction. Therefore, st−γpr(T
′) = 2∆.
Hence, the tree T ′ satisfies ∆(T ′) = ∆, γpr(T ′) ≥ 4 and st−γpr(T
′) = 2∆. Proceeding
by induction, we have T ′ ∈ F∆. Thus, T ′ is constructed from the disjoint union of k′
double stars each isomorphic to S(∆− 1,∆− 1), by selecting one leaf from each double
star and adding k′−1 edges between these selected leaves to produce a tree with maximum
degree ∆. The resulting tree T ′ satisfies γpr(T ′) = 2k′ with the 2k′ support vertices
forming a γpr-set of T ′.
By construction of T ′, the tree T ′ contains the vertex v4 but not the vertex v3. Sup-
pose that v4 is a support vertex in T ′, implying by construction of T ′ that v4 is a vertex
of degree ∆ in T ′. Let S = (N [v1] ∪ N [v2]) \ {v3}. We note that S ∈ NI(T ) and
|S| = 2∆ − 1. Let D′ be the (unique) γpr-set of T ′, and so D′ is the set of 2k′ support
vertices in T ′. In particular, we note that v4 ∈ D′. The set D′ is a PD-set of T − S, and
so γpr(T − S) ≤ |D′| = γpr(T ′) = γpr(T ) − 2. Therefore, st−γpr(T ) ≤ |S| = 2∆ − 1,
a contradiction. Hence, v4 is a leaf of T ′, and so v4 is a leaf in one of the k′ double stars in
the construction of T ′. Selecting the leaf v4 from this double star and selecting the leaf v3
from the double star induced by N [v1] ∪N [v2], which is isomorphic to S(∆− 1,∆− 1),
and adding back the edge v3v4 we re-construct the tree T , showing that T ∈ F∆. This
completes the proof of part (a).
Part (b) now follows readily from part (a). If T ∈ F∆ for some ∆ ≥ 2, then by Lem-
mas 6.1 and 6.3, we have stγpr(T ) ≤ ∆− 1. Hence, we may assume that T /∈ F∆ for any
∆ ≥ 2, for otherwise the bound in part (b) is immediate. With this assumption, the upper
bound in part (b) follows immediately from part (a) noting that stγpr(T ) ≤ st−γpr(T ) ≤
2∆− 1. That the bound is tight for all ∆ ≥ 2 follows from Proposition 3.1.
8 Proof of Theorem 2.3
In this section we present a proof of Theorem 2.3, which we restate below.
Theorem 2.3. If G is a connected graph with γpr(G) ≥ 4, then st−γpr(G) ≤ 2∆(G), and
this bound is sharp.
Proof. Let G be a connected graph with γpr(G) ≥ 4 and let ∆ = ∆(G). Since
γpr(G) ≥ 4, we have ∆ ≥ 2. If ∆ = 2, then G is a path Pn or a cycle Cn, and
by Theorem 5.1, we have st−γpr(G) ≤ 2∆, with equality if and only if n ≡ 0 (mod 4).
Assume, therefore, that ∆ ≥ 3.
Let T be a spanning tree of G such that γpr(T ) = γpr(G). We note that such a tree ex-
ists by Lemma 4.1. Let S be a st−γpr -set of T . Thus, S is a set in NI(T ) with
|S| = st−γpr(T ) such that γpr(T − S) < γpr(T ). By Observation 4.2, we have
A. Gorzkowska et al.: Paired domination stability in graphs 247
|S| = st−γpr(T ) ≤ n − 2. Since S ∈ NI(T ), every vertex in T − S, and therefore in
the supergraph G − S, has degree at least 1. Hence, S ∈ NI(G) and since γpr(G − S) ≤
γpr(T − S), we have γpr(G − S) < γpr(G). Thus, st−γpr(G) ≤ |S| = st
−
γpr(T ). By The-
orem 2.2, we have st−γpr(T ) ≤ 2∆(T ). Noting that ∆(T ) ≤ ∆(G), we therefore have that
st−γpr(G) ≤ st
−
γpr(T ) ≤ 2∆(T ) ≤ 2∆(G) = 2∆.
To show that the upper bound in Theorem 2.3 is tight, we present a family of graphs
with maximum degree ∆ and γpr(G) ≥ 4 satisfying st−γpr(G) = 2∆. Our first family, G∆,
is constructed as follows. For k ≥ 2 and ∆ ≥ 2, let Gk,∆ be a graph obtained from k
double stars S(∆ − 1,∆ − 1) by choosing two leaves at distance 3 apart in each double
star and adding k edges between the chosen leaves in such a way, that every chosen vertex
has degree 2 in the resulting graph. Let G∆ be the family of all such graphs Gk,∆ for
all k ≥ 2. The graph G2,6 ∈ G6, for example, is illustrated in Figure 5. We note that
γpr(Gk,∆) = 2k and that set of 2k vertices of degree ∆ is the unique γpr-set of Gk,∆.
Furthermore, st−γpr(Gk,∆) = 2∆.



 



















Figure 5: The graph G2,6 from a class of graphs Gk,∆.
Recall that by definition we have stγpr(G) ≤ st−γpr(G) for every graph G. Hence, as an
immediate consequence of Theorem 2.3 we have Corollary 2.4. Recall its statement.
Corrolary 2.4. If G is a connected graph with γpr(G) ≥ 4, then stγpr(G) ≤ 2∆(G).
It remains an open problem, however, to determine if the upper bound of Corollary 2.4
is best achievable for all values of possible value of ∆(G) = ∆ ≥ 2. If ∆ = 2 and G is
a path, then G ∼= Pn where n ≥ 5, and stγpr(G) ≤ 2∆ − 2 by Corollary 5.3. If ∆ = 2
and G is a cycle, then G ∼= Cn where n ≥ 5, and stγpr(G) ≤ 2∆ by Corollary 5.5,
with equality if and only if G = C8. Hence, the only connected graph G with maximum
degree ∆ = 2 satisfying γpr(G) ≥ 4 and stγpr(G) = 2∆ is the 8-cycle, namely G = C8.
For ∆ ≥ 3, we do not know of a connected graph G with maximum degree ∆ satisfying
γpr(G) ≥ 4 and stγpr(G) = 2∆.
By Corollary 5.5 and Proposition 3.1, for any given ∆ ≥ 2, there do exists infinite
families of connected graphs G with maximum degree ∆ satisfying stγpr(G) = 2∆ − 1.
Thus, if the upper bound of Corollary 2.4 can be improved to stγpr(G) ≤ 2∆ − 1 in the
case when ∆ ≥ 3, then this bound would be tight.
ORCID iDs
Aleksandra Gorzkowska https://orcid.org/0000-0001-5335-7351
Michael A. Henning https://orcid.org/0000-0001-8185-067X
248 Ars Math. Contemp. 22 (2022) #P2.04 / 231–248
Monika Pilśniak https://orcid.org/0000-0002-3734-7230
Elżbieta Tumidajewicz https://orcid.org/0000-0002-1413-2413
References
[1] M. Amraee, N. Jafari Rad and M. Maghasedi, Roman domination stability in graphs, Math.
Rep. (Bucur.) 21 (2019), 193–204, http://imar.ro/journals/Mathematical\
_Reports/php/2019/Mrc19\_2.php.
[2] A. Aytaç and B. Atay Atakul, Exponential domination critical and stability in some graphs, Int.
J. Found. Comput. Sci. 30 (2019), 781–791, doi:10.1142/s0129054119500217.
[3] D. Bauer, F. Harary, J. Nieminen and C. L. Suffel, Domination alteration sets in graphs, Discrete
Math. 47 (1983), 153–161, doi:10.1016/0012-365x(83)90085-7.
[4] R. C. Brigham, P. Z. Chinn and R. D. Dutton, Vertex domination-critical graphs, Networks 18
(1988), 173–179, doi:10.1002/net.3230180304.
[5] R. C. Brigham, T. W. Haynes, M. A. Henning and D. F. Rall, Bicritical domination, Discrete
Math. 305 (2005), 18–32, doi:10.1016/j.disc.2005.09.013.
[6] T. Burton and D. P. Sumner, Domination dot-critical graphs, Discrete Math. 306 (2006), 11–18,
doi:10.1016/j.disc.2005.06.029.
[7] W. J. Desormeaux, T. W. Haynes and M. A. Henning, Total domination changing and stable
graphs upon vertex removal, Discrete Appl. Math. 159 (2011), 1548–1554, doi:10.1016/j.dam.
2011.06.006.
[8] W. J. Desormeaux, T. W. Haynes and M. A. Henning, Paired domination in graphs, in: T. W.
Haynes, S. T. Hedetniemi and M. A. Henning (eds.), Topics in Domination in Graphs, Springer,
Cham, volume 64 of Dev. Math., pp. 31–77, 2020, doi:10.1007/978-3-030-51117-3\_3.
[9] O. Favaron, D. P. Sumner and E. Wojcicka, The diameter of domination k-critical graphs, J.
Graph Theory 18 (1994), 723–734, doi:10.1002/jgt.3190180708.
[10] T. W. Haynes, S. T. Hedetniemi and M. A. Henning (eds.), Topics in Domination in
Graphs, volume 64 of Developments in Mathematics, Springer, Cham, 2020, doi:10.1007/
978-3-030-51117-3.
[11] T. W. Haynes and P. J. Slater, Paired-domination in graphs, Networks 32 (1998), 199–206,
doi:10.1002/(sici)1097-0037(199810)32:3<199::aid-net4>3.0.co;2-f.
[12] M. A. Henning and M. Krzywkowski, Total domination stability in graphs, Discrete Appl.
Math. 236 (2018), 246–255, doi:10.1016/j.dam.2017.07.022.
[13] M. A. Henning and N. J. Rad, On total domination vertex critical graphs of high connectivity,
Discrete Appl. Math. 157 (2009), 1969–1973, doi:10.1016/j.dam.2008.12.009.
[14] M. A. Henning and A. Yeo, Total Domination in Graphs, Springer Monographs in Mathemat-
ics, Springer, New York, 2013, doi:10.1007/978-1-4614-6525-6.
[15] N. Jafari Rad, E. Sharifi and M. Krzywkowski, Domination stability in graphs, Discrete Math.
339 (2016), 1909–1914, doi:10.1016/j.disc.2015.12.026.
[16] Z. Li, Z. Shao and S.-j. Xu, 2-rainbow domination stability of graphs, J. Comb. Optim. 38
(2019), 836–845, doi:10.1007/s10878-019-00414-0.
[17] D. P. Sumner, Critical concepts in domination, Discrete Math. 86 (1990), 33–46, doi:10.1016/
0012-365x(90)90347-k.
[18] D. P. Sumner and P. Blitch, Domination critical graphs, J. Comb. Theory Ser. B 34 (1983),
65–76, doi:10.1016/0095-8956(83)90007-2.