Domination in partitioned graphs with minimum degree two

Michael A. Henning, Preben Dahl Vestergaard

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Let V1, V2 be a partition of the vertex set in a graph G. For i = 1, 2, let γi denote the least number of vertices needed in G to dominate Vi. It is known that if G has order n and minimum degree two, then γ1 + γ2 ≤ 2 n / 3. In this paper, we characterize those graphs of order n which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and γ1 + γ2 = 2 n / 3.

Original languageEnglish
Pages (from-to)1115-1135
Number of pages21
JournalDiscrete Mathematics
Issue number9-10
Publication statusPublished - 6 May 2007
Externally publishedYes


  • 3-subdivision
  • Domination
  • Minimum degree two
  • Partitioned graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Domination in partitioned graphs with minimum degree two'. Together they form a unique fingerprint.

Cite this