Domination versus edge domination

2019/06/25 by Baste, Julien, Fürst, Maximilian, Henning, Michael A. +2
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1906.10420

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+(2(Δ-1))/(Δ2^Δ))γ_e(G) for general Δ≥ 1, and γ(G)≤ ((7)/(6)-(1)/(204))γ_e(G) for Δ=3. Furthermore, we verify our conjecture for cubic claw-free graphs.

Related

• 1/2-conjectures on the domination game and claw-free graphs
• Domination versus independent domination in regular graphs
• Changing of the domination number of a graph: edge multisubdivision and edge removal
• The sub-k-domination number of a graph with applications to k-domination
• A note on the independent domination number versus the domination number in bipartite graphs