On the Paired-Domination Subdivision Number of a Graph

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(gamma pr)(G) of G. It is well known that sd(gamma pr)(G+e) can be smaller or larger than sd(gamma pr)(G) for some edge e is not an element of E(G). In this note, we show that, if G is an isolated-free graph different from mK(2), then, for every edge e is not an element of E(G), sd(gamma pr)(G + e) <= sd(gamma pr)(G) + 2 Delta(G).

Automated summary

This paper proves that if a graph G is isolated-free and not mK(2), then for every edge e not in E(G), the paired-domination subdivision number of G with e added will not exceed the original number plus twice the maximum degree of G.