## Abstract

A set S of vertices in a graph G is a dominating set of G if every vertex of V (G) {set minus} S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ (G). Let P_{n} and C_{n} denote a path and a cycle, respectively, on n vertices. Let k_{1} (F) and k_{2} (F) denote the number of components of a graph F that are isomorphic to a graph in the family {P_{3}, P_{4}, P_{5}, C_{5}} and {P_{1}, P_{2}}, respectively. Let L be the set of vertices of G of degree more than 2, and let G - L be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd [W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n ≥ 8 with δ (G) ≥ 2, then γ (G) ≤ 2 n / 5, while Reed [B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ (G) ≥ 3, then γ (G) ≤ 3 n / 8. As an application of Reed's result, we show that if G is a graph of order n ≥ 14 with δ (G) ≥ 2, then γ (G) ≤ frac(3, 8) n + frac(1, 8) k_{1} (G - L) + frac(1, 4) k_{2} (G - L).

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

Pages (from-to) | 639-646 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 309 |

Issue number | 4 |

DOIs | |

Publication status | Published - 6 Mar 2009 |

Externally published | Yes |

## Keywords

- Bounds
- Domination number
- Path-component

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics