A new bound on the domination number of graphs with minimum degree two

Michael A. Henning, Ingo Schiermeyer, Anders Yeo

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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, Cx, which is an induced 4-cycle and x is adjacent to at least one but at most three vertices on Cx. 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 (C4,C5)-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 (C4,C5)-free, then γ(G) ≤ 3n/8; (iv) if G is 2-connected and dG(u) + dG(v) ≥ 5 for every two adjacent vertices u and v, then γ(G) ≤ 3n/8. All bounds are sharp.

Original languageEnglish
Pages (from-to)1-35
Number of pages35
JournalElectronic Journal of Combinatorics
Issue number1
Publication statusPublished - 2011


  • Bounds
  • Cycles
  • Domination number

ASJC Scopus subject areas

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


Dive into the research topics of 'A new bound on the domination number of graphs with minimum degree two'. Together they form a unique fingerprint.

Cite this