Enumerating minimal dominating sets in chordal graphs

•A structural theorem about the distribution of simplicial vertices in a chordal graph.•An algorithm for enumerating minimal dominating sets in a chordal graph.•Upper bound on number of minimal dominating sets improved from 1.6181n to 1.5214n. The maximum number of minimal dominating sets in a chord...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2016-12, Vol.116 (12), p.739-743
Main Authors: Abu-Khzam, Faisal N., Heggernes, Pinar
Format: Article
Language:English
Subjects:
Branching algorithm
Chordal graphs
Graph algorithms
Graph theory
Information processing
Input sensitive enumeration
Maximum number of minimal dominating sets
Set theory
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•A structural theorem about the distribution of simplicial vertices in a chordal graph.•An algorithm for enumerating minimal dominating sets in a chordal graph.•Upper bound on number of minimal dominating sets improved from 1.6181n to 1.5214n. 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.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2016.07.002