On the Paired-Domination Subdivision Number of Trees

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 gammapr(G) of G. The paired-domination subdivision number sdgammapr(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 not equal P5 of order n >= 3 and each edge e is not an element of E(T), sdgammapr(T) + sdgammapr(T + e) <= n + 2.

Automated summary

The research examines the characteristics of paired-dominating sets in graphs and proves that there is an upper bound on the number of edges that need to be subdivided in order to increase the paired-domination number for certain types of trees.