Diameter of paired domination edge-critical graphs

A paired dominating set of a graph G without isolated vertices is a dominating set of G whose induced subgraph has a perfect matching. The paired domination number γ_pr(G) of G is the minimum cardinality amongst all paired dominating sets of G. Thegraph G is paired domination edge-critical (γ_prEC) if for every e ∈ E(Ḡ), γ_pr(G + e) < γ_pr(G). We investigate the diameter of γ_prEC graphs. To this effect we characterize γ_prEC trees. We show that for arbitrary even k ≥ 4 there exists a k_prEC graph with diameter two. We provide an example which shows that the maximum diameter of a k_prEC graph is at least k - 2 and prove that it is at most min{2k - 6, 3k/2 + 3}.