On the Paired-Domination Subdivision Number of a Graph

Abstract

In order to increase the paired-domination number of a graph G, the minimum number of edges that must be subdivided (where each edge in G can be subdivided no more than once) is called the paired-domination subdivision number sdγpr(G) of G. It is well known that sdγpr(G+e) can be smaller or larger than sdγpr(G) for some edge e∉E(G). In this note, we show that, if G is an isolated-free graph different from mK2, then, for every edge e∉E(G), sdγpr(G+e)≤sdγpr(G)+2Δ(G).

Keywords

• paired-domination number
• paired-domination subdivision number