Bounds on the Semipaired Domination Number of Graphs With Minimum Degree at Least Two
Document Type
Article
Publication Date
2-1-2021
Description
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.
Citation Information
Haynes, Teresa W.; and Henning, Michael A.. 2021. Bounds on the Semipaired Domination Number of Graphs With Minimum Degree at Least Two. Journal of Combinatorial Optimization. Vol.41(2). 451-486. https://doi.org/10.1007/s10878-020-00687-w ISSN: 1382-6905