Block Graphs with Large Paired Domination Multisubdivision Number

Abstract

The paired domination multisubdivision number of a nonempty graph G, denoted by msdpr(G), is the smallest positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. It is known that msdpr(G) ≤ 4 for all graphs G. We characterize block graphs with msdpr(G) = 4.

Keywords

• paired domination
• domination subdivision number
• domination multisubdivision number
• block graph
• 05c69