Enumerating minimal dominating sets in chordal graphs

Faisal N. Abu-Khzam, Pinar Heggernes

    Research output: Contribution to journalArticle

    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.

    Original languageEnglish
    Pages (from-to)739-743
    Number of pages5
    JournalInformation Processing Letters
    Volume116
    Issue number12
    DOIs
    Publication statusPublished - 1 Dec 2016

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

  • Cite this