Minimal dominating sets in interval graphs and trees

详细信息    查看全文

• 作者：Petr A. Golovach^a ; ^{petr.golovach@uib.no} ; Pinar Heggernes^a ; ^{pinar.heggernes@uib.no} ; Mamadou Moustapha Kanté ; ^b ; ^{mamadou.kante@isima.fr} ; Dieter Kratsch^c ; ^{dieter.kratsch@univ-lorraine.fr} ; Yngve Villanger^a ; ^{yngve.villanger@gmail.com}
• 关键词：Graphs ; Minimal dominating sets ; Graph classes ; Enumeration
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：162-170
• 全文大小：412 K
• 卷排序：216

文摘

We show that interval graphs on nn vertices have at most 3n/3≈1.4422n3n/3≈1.4422n minimal dominating sets, and that these can be enumerated in time O∗(3n/3)O∗(3n/3). As there are examples of interval graphs that actually have 3n/33n/3 minimal dominating sets, our bound is tight. We show that the same upper bound holds also for trees, i.e. trees on nn vertices have at most 3n/3≈1.4422n3n/3≈1.4422n minimal dominating sets. The previous best upper bound on the number of minimal dominating sets in trees was 1.4656n1.4656n, and there are trees that have 1.4167n1.4167n minimal dominating sets. Hence our result narrows this gap. On general graphs there is a larger gap, with 1.7159n1.7159n being the best known upper bound, whereas no graph with 1.5705n1.5705n or more minimal dominating sets is known.