## Abstract

Let G=(V,E) be a graph. A set S-V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted γ _{r} (G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then γ_{r}(G) ≥ n/4, and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then γ_{r}(G)≤ 5n/11. Lastly, we show that if G is a claw-free cubic graph, then γ _{r} (G)=γ(G).

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

Pages (from-to) | 166-179 |

Number of pages | 14 |

Journal | Journal of Combinatorial Optimization |

Volume | 22 |

Issue number | 2 |

DOIs | |

Publication status | Published - Aug 2011 |

## Keywords

- Cubic graph
- Domination
- Graph
- Lower bound
- Restrained domination
- Upper bound

## ASJC Scopus subject areas

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