## Abstract

A vertex in G is said to dominate itself and its neighbors. A subset S of vertices is a dominating set if S dominates every vertex of G. A paired-dominating set is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γ _{pr}(G), is the minimum cardinality of a paired-dominating set in G. A subset S⊆V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ _{×2}(G). A claw-free graph is a graph that does not contain K _{1,3} as an induced subgraph. Chellali and Haynes (Util. Math. 67:161-171, 2005) showed that for every claw-free graph G, we have γ _{pr}(G)≤ γ×2 (G). In this paper we extend this result by showing that for r≥2, if G is a connected graph that does not contain K _{1,r} as an induced subgraph, then γ_{pr}(G) ≤ (2r^{2}-6r+6/r(r-1) γ _{×2}(G).

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

Pages (from-to) | 688-694 |

Number of pages | 7 |

Journal | Journal of Combinatorial Optimization |

Volume | 27 |

Issue number | 4 |

DOIs | |

Publication status | Published - May 2014 |

## Keywords

- Claw-free
- Double domination
- Paired-domination

## ASJC Scopus subject areas

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

## Fingerprint

Dive into the research topics of 'Paired versus double domination in K_{1,r}-free graphs'. Together they form a unique fingerprint.