Towards the Conjecture on Domination Versus Edge Domination in Graphs

被引：1

作者：

Maniya, Paras ^{[1
]}

Pradhan, Dinabandhu ^{[1
]}

机构：

[1] Indian Inst Technol ISM, Dept Math & Comp, Dhanbad, India

来源：

BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY | 2024年 / 47卷 / 01期

关键词：

Domination; Edge domination; Minimum maximal matching; Fork-free graphs;

D O I：

10.1007/s40840-023-01626-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Baste et al. (Discrete Appl Math 285:343-349, 2020) conjectured that the domination number gamma(G) of a Delta-regular graph G with Delta >= 1 is at most its edge domination number gamma(e)(G). They also verified that the conjecture is true for 3-regular claw-free graphs. Civan et al. (Discrete Appl Math 337:171-172, 2023) generalize the result of Baste et al. (Discrete Appl Math 285:343-349, 2020) by proving that gamma(G) <= gamma(e)( G) if G is a claw-free graph with minimum degree at least two. In this paper, we show that if G is a fork-free graph with minimum degree at least two, then the domination number of G is at most its edge domination number. This generalizes the previous results on the conjecture. We also prove that gamma(G) <= gamma(e)(G) if G is a P-4-free graph with minimum degree at least one.

引用

页数：7