## Abstract

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199-206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _{pr}(G), is the minimum cardinality of a paired-dominating set of G. The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one, γ _{pr}(G - v) < γ _{pr}(G). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least 3/2 (γ _{pr}(G) - 2). For γ _{pr}(G) ≤ 8, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph.

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

Pages (from-to) | 887-897 |

Number of pages | 11 |

Journal | Czechoslovak Mathematical Journal |

Volume | 58 |

Issue number | 4 |

DOIs | |

Publication status | Published - Dec 2008 |

Externally published | Yes |

## Keywords

- Bounds
- Diameter
- Paired-domination
- Vertex critical

## ASJC Scopus subject areas

- General Mathematics