Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950954 | Information Processing Letters | 2016 | 5 Pages |
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
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Faisal N. Abu-Khzam, Pinar Heggernes,