## Abstract

For a graph G, let γ(G) denote the domination number of G and let δ(G) denote the minimum degree among the vertices of G. A vertex x is called a bad-cut-vertex of G if G-x contains a component, C_{x}, which is an induced 4-cycle and x is adjacent to at least one but at most three vertices on C_{x}. A cycle C is called a special-cycle if C is a 5-cycle in G such that if u and v are consecutive vertices on C, then at least one of u and v has degree 2 in G. We let bc(G) denote the number of bad-cut-vertices in G, and sc(G) the maximum number of vertex disjoint special-cycles in G that contain no bad-cut-vertices. We say that a graph is (C_{4},C_{5})-free if it has no induced 4-cycle or 5-cycle. Bruce Reed [14] showed that if G is a graph of order n with δ(G) ≥ 3, then γ(G) ≤ 3n/8. In this paper, we relax the minimum degree condition from three to two. Let G be a connected graph of order n ≥ 14 with δ(G) ≥ 2. As an application of Reed's result, we show that γ(G) ≤ 1/8 (3n + sc(G) + bc(G)). As a consequence of this result, we have that (i) γ(G) ≤ 2n/5; (ii) if G contains no special-cycle and no bad-cut-vertex, then γ(G) ≤ 3n/8; (iii) if G is (C_{4},C_{5})-free, then γ(G) ≤ 3n/8; (iv) if G is 2-connected and d_{G}(u) + d_{G}(v) ≥ 5 for every two adjacent vertices u and v, then γ(G) ≤ 3n/8. All bounds are sharp.

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

Pages (from-to) | 1-35 |

Number of pages | 35 |

Journal | Electronic Journal of Combinatorics |

Volume | 18 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2011 |

## Keywords

- Bounds
- Cycles
- Domination number

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics