Domination versus edge domination

DOI10.1016/J.DAM.2020.05.030MaRDI QIDQ2197443zbMATH OpenOpenAlexWikidataFDO

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

Publication date 31 August 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.10420

zbMATH Keywords

dominationedge dominationminimum maximal matching

Mathematics Subject Classification ID

Vertex degrees (05C07) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We propose the conjecture that the domination number $gamma(G)$ of a $Delta$-regular graph $G$ with $Deltageq1$ is always at most its edge domination number $gamm{a}_e(G)$, which coincides with the domination number of its line graph. We prove that $gamma(G)leqleft(1+frac2(Delta-1)Delta{2}^{Delta}ight)gamm{a}_e(G)$ for general $Deltageq1$, and $gamma(G)leqleft(frac76-frac1204ight)gamm{a}_e(G)$ for $Delta=3$. Furthermore, we verify our conjecture for cubic claw-free graphs.

Review text

In this paper, the authors establish a conjecture about the relationship of domination number and edge domination number of a $\Delta$-regular graph $G$ with $\Delta\geq 1$. Moreover, they obtain three results related to this conjecture where $G$ is a $\Delta$-regular graph with $\Delta\geq 1$, $G$ is a cubic graph and $G$ is a cubic claw-free graph, respectively.

Recommendations

• Domination versus edge domination on claw-free graphs
• On domination in 2-connected cubic graphs
• On domination in connected cubic graphs
• Domination versus independent domination in graphs of small regularity
• On a conjecture on total domination in claw-free cubic graphs

Cites work

• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
• Approximating edge dominating set in dense graphs
• Approximation hardness of edge dominating set problems
• Edge Dominating Sets in Graphs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Integer programming formulations for the minimum weighted maximal matching problem
• Minimum Edge Dominating Sets
• On domination and independent domination numbers of a graph
• The probabilistic method

Cited in

(11)

• Disproofs of three conjectures on the power domination of graphs
• Edge domination in grids
• A NOT ON DOMINATING SET WITH MAPLE
• scientific article; zbMATH DE number 2147928 (Why is no real title available?)
• Majority bad number
• Conjectures of TxGraffiti: independence, domination, and matchings
• Domination versus edge domination on claw-free graphs
• Towards the conjecture on domination versus edge domination in graphs
• Dominating sets, packings, and the maximum degree
• Minimum maximal matchings in phenylene chains
• Power domination in regular claw-free graphs

This page was built for publication: Domination versus edge domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197443)