## 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 minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by γ_{pr}(G). If G does not contain a graph F as an induced subgraph, then G is said to be F-free. In particular if F = K_{1,3}, or K_{4} - e, then we say that G is claw-free or diamond-free, respectively. Let G be a connected cubic graph of order n. We show that (i) if G is (K_{1,3}, K_{4} - e, C_{4})-free, then γ_{pr}(G) ≤ 3n/8; (ii) if G is claw-free and diamond-free, then γ_{pr}(G) ≤ 2n/5; (iii) if G is claw-free, then γ_{pr}(G) ≤ n/2. In all three cases, the extremal graphs are characterized.

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

Pages (from-to) | 447-456 |

Number of pages | 10 |

Journal | Graphs and Combinatorics |

Volume | 20 |

Issue number | 4 |

DOIs | |

Publication status | Published - Nov 2004 |

Externally published | Yes |

## Keywords

- Bounds
- Claw-free cubic graphs
- Paired-domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics