## Abstract

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γ_{pr}(G). We establish bounds on Γ_{pr}(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γ_{pr}(G)≥4n/5 if δ=1 and n≥3, Γ_{pr}(G)≥3n/4 if δ=2 and n≥6, and Γ_{pr}(G)≥2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γ_{pr}(G)=4n/ 5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γ_{pr}(G)=3n/4 are characterized.

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

Pages (from-to) | 235-251 |

Number of pages | 17 |

Journal | Journal of Combinatorial Optimization |

Volume | 22 |

Issue number | 2 |

DOIs | |

Publication status | Published - Aug 2011 |

Externally published | Yes |

## Keywords

- Claw-free graphs
- Minimum degree
- Upper paired-domination

## ASJC Scopus subject areas

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics