## Abstract

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 (γ_{pr}EC) if for every e ∈ E(Ḡ), γ_{pr}(G + e) < γ_{pr}(G). We investigate the diameter of γ_{pr}EC graphs. To this effect we characterize γ_{pr}EC trees. We show that for arbitrary even k ≥ 4 there exists a k_{pr}EC graph with diameter two. We provide an example which shows that the maximum diameter of a k_{pr}EC graph is at least k - 2 and prove that it is at most min{2k - 6, 3k/2 + 3}.

Original language | English |
---|---|

Pages (from-to) | 279-291 |

Number of pages | 13 |

Journal | Australasian Journal of Combinatorics |

Volume | 40 |

Publication status | Published - 2008 |

Externally published | Yes |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics