Enumerating minimal dominating sets in chordal graphs

Faisal N. Abu-Khzam, Pinar Heggernes

    Research output: Contribution to journal › Article › Research › peer-review

    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

    Chordal Graphs
    Minimal Set
    Dominating Set
    Upper and Lower Bounds

    Cite this

    Abu-Khzam, Faisal N. ; Heggernes, Pinar. / Enumerating minimal dominating sets in chordal graphs. In: Information Processing Letters. 2016 ; Vol. 116, No. 12. pp. 739-743.
    @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 = "12",
    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",

    }

    Abu-Khzam, FN & Heggernes, P 2016, 'Enumerating minimal dominating sets in chordal graphs', Information Processing Letters, vol. 116, no. 12, pp. 739-743. https://doi.org/10.1016/j.ipl.2016.07.002

    Enumerating minimal dominating sets in chordal graphs. / Abu-Khzam, Faisal N.; Heggernes, Pinar.

    In: Information Processing Letters, Vol. 116, No. 12, 01.12.2016, p. 739-743.

    Research output: Contribution to journal › Article › Research › peer-review

    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

    VL - 116

    SP - 739

    EP - 743

    JO - Information Processing Letters

    JF - Information Processing Letters

    SN - 0020-0190

    IS - 12

    ER -

    Abu-Khzam FN, Heggernes P. Enumerating minimal dominating sets in chordal graphs. Information Processing Letters. 2016 Dec 1;116(12):739-743. https://doi.org/10.1016/j.ipl.2016.07.002

    Access to Document