Domination versus edge domination

Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr, Dieter Rautenbach

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


We propose the conjecture that the domination number γ(G) of a Δ-regular graph G with Δ≥1 is always at most its edge domination number γe(G), which coincides with the domination number of its line graph. We prove that γ(G)≤1+[Formula presented]γe(G) for general Δ≥1, and γ(G)≤[Formula presented]γe(G) for Δ=3. Furthermore, we verify our conjecture for cubic claw-free graphs.

Original languageEnglish
Pages (from-to)343-349
Number of pages7
JournalDiscrete Applied Mathematics
Publication statusPublished - 15 Oct 2020


  • Domination
  • Edge domination
  • Minimum maximal matching

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Domination versus edge domination'. Together they form a unique fingerprint.

Cite this