Domination versus edge domination

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

doi:10.1016/j.dam.2020.05.030

Domination versus edge domination

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

Mathematics and Applied Mathematics

Ulm University

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	343-349
Number of pages	7
Journal	Discrete Applied Mathematics
Volume	285
DOIs	https://doi.org/10.1016/j.dam.2020.05.030
Publication status	Published - 15 Oct 2020

Keywords

Domination
Edge domination
Minimum maximal matching

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2020.05.030

Cite this

@article{3e082f1a1c1948bfafe1623a504382c3,

title = "Domination versus edge domination",

abstract = "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.",

keywords = "Domination, Edge domination, Minimum maximal matching",

author = "Julien Baste and Maximilian F{\"u}rst and Henning, {Michael A.} and Elena Mohr and Dieter Rautenbach",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = oct,

day = "15",

doi = "10.1016/j.dam.2020.05.030",

language = "English",

volume = "285",

pages = "343--349",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Domination versus edge domination

AU - Baste, Julien

AU - Fürst, Maximilian

AU - Henning, Michael A.

AU - Mohr, Elena

AU - Rautenbach, Dieter

PY - 2020/10/15

Y1 - 2020/10/15

N2 - 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.

AB - 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.

KW - Domination

KW - Edge domination

KW - Minimum maximal matching

UR - http://www.scopus.com/inward/record.url?scp=85086599676&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.05.030

DO - 10.1016/j.dam.2020.05.030

M3 - Article

AN - SCOPUS:85086599676

SN - 0166-218X

VL - 285

SP - 343

EP - 349

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Domination versus edge domination

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this