On the Paired-Domination Subdivision Number of Trees

Abstract

A paired-dominating set of a graph G without isolated vertices is a dominating set of vertices whose induced subgraph has perfect matching. The minimum cardinality of a paired-dominating set of G is called the paired-domination number γpr(G) of G. The paired-domination subdivision number sdγpr(G) of G 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. Here, we show that, for each tree T ≠ P5 of order n ≥ 3 and each edge e ∉ E(T), sdγpr(T) + sdγpr(T + e) ≤ n + 2.

Keywords

• paired-domination number
• paired-domination subdivision number