Let G be a graph with vertex set V and no isolated vertices. A subset S ⊆ V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. We present a method of building trees having a unique minimum semipaired dominating set.

Let G be a graph with vertex set V. A subset S ? V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number is the minimum cardinality of a semipaired dominating set of G. We characterize the trees having a unique minimum semipaired dominating set. We also determine an upper bound on the semipaired domination number of these trees and characterize the trees attaining this bound.

Let G be a graph with vertex set V and no isolated vertices. A subset S⊆ V is a semipaired dominating set of G if every vertex in V\ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number γpr 2(G) is the minimum cardinality of a semipaired dominating set of G. We show that if G is a connected graph of order n with minimum degree at least 2, then γpr2(G)≤12(n+1). Further, we show that if n≢3(mod4), then γpr2(G)≤12n, and we show that for every value of n≡3(mod4), there exists a connected graph G of order n with minimum degree at least 2 satisfying γpr2(G)=12(n+1). As a consequence of this result, we prove that every graph G of order n with minimum degree at least 3 satisfies γpr2(G)≤12n.