Diameter of paired domination edge-critical graphs
Michelle Edwards, Richard G. Gibson, Michael A. Henning, Christina M. Mynhardt · Australas. J Comb. · 2008
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. The graph G is paired domination edge-critical (γprEC) if for every e ∈ E(G), γ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 kprEC graph with diameter two. We provide an example which shows that the maximum diameter of a kprEC graph is at least k −2 and prove that it is at most min{2k − 6,3k/2 + 3}.