Enumerating minimal dominating sets in chordal graphs

Faisal N. Abu-Khzam; Pinar Heggernes

doi:10.1016/j.ipl.2016.07.002

Enumerating minimal dominating sets in chordal graphs

Faisal N. Abu-Khzam, Pinar Heggernes

Research output: Contribution to journal › Article

Abstract

The maximum number of minimal dominating sets in a chordal graph on n vertices is known to be at most 1.6181ⁿ. However, no example of a chordal graph with more than 1.4422ⁿ minimal dominating sets is known. In this paper, we narrow this gap between the known upper and lower bounds by showing that the maximum number of minimal dominating sets in a chordal graph is at most 1.5214ⁿ.

Original language	English
Pages (from-to)	739-743
Number of pages	5
Journal	Information Processing Letters
Volume	116
Issue number	12
DOIs	https://doi.org/10.1016/j.ipl.2016.07.002
Publication status	Published - 1 Dec 2016

Access to Document

10.1016/j.ipl.2016.07.002

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Enumerating minimal dominating sets in chordal graphs'. Together they form a unique fingerprint.

Cite this

@article{8b0b3b922dc64cb8b4d9ca6684b25fbc,

title = "Enumerating minimal dominating sets in chordal graphs",

abstract = "The maximum number of minimal dominating sets in a chordal graph on n vertices is known to be at most 1.6181n. However, no example of a chordal graph with more than 1.4422n minimal dominating sets is known. In this paper, we narrow this gap between the known upper and lower bounds by showing that the maximum number of minimal dominating sets in a chordal graph is at most 1.5214n.",

keywords = "Branching algorithm, Chordal graphs, Graph algorithms, Input sensitive enumeration, Maximum number of minimal dominating sets",

author = "Abu-Khzam, {Faisal N.} and Pinar Heggernes",

year = "2016",

month = dec,

day = "1",

doi = "10.1016/j.ipl.2016.07.002",

language = "English",

volume = "116",

pages = "739--743",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "12",

}

TY - JOUR

T1 - Enumerating minimal dominating sets in chordal graphs

AU - Abu-Khzam, Faisal N.

AU - Heggernes, Pinar

PY - 2016/12/1

Y1 - 2016/12/1

N2 - The maximum number of minimal dominating sets in a chordal graph on n vertices is known to be at most 1.6181n. However, no example of a chordal graph with more than 1.4422n minimal dominating sets is known. In this paper, we narrow this gap between the known upper and lower bounds by showing that the maximum number of minimal dominating sets in a chordal graph is at most 1.5214n.

AB - The maximum number of minimal dominating sets in a chordal graph on n vertices is known to be at most 1.6181n. However, no example of a chordal graph with more than 1.4422n minimal dominating sets is known. In this paper, we narrow this gap between the known upper and lower bounds by showing that the maximum number of minimal dominating sets in a chordal graph is at most 1.5214n.

KW - Branching algorithm

KW - Chordal graphs

KW - Graph algorithms

KW - Input sensitive enumeration

KW - Maximum number of minimal dominating sets

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

U2 - 10.1016/j.ipl.2016.07.002

DO - 10.1016/j.ipl.2016.07.002

M3 - Article

AN - SCOPUS:84989830093

VL - 116

SP - 739

EP - 743

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 12

ER -