Enumerating minimal dominating sets in chordal graphs
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 th...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | article |
| Published: |
2016
|
| Online Access: | http://hdl.handle.net/10725/4760 http://dx.doi.org/10.1016/j.ipl.2016.07.002 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0020019016301004 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513464562614272 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Heggernes, Pinar |
| author2_role | author |
| author_facet | Abu-Khzam, Faisal N. Heggernes, Pinar |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Heggernes, Pinar |
| dc.date.none.fl_str_mv | 2016-11-08T14:05:49Z 2016-11-08T14:05:49Z 2016 2016-11-08 |
| dc.identifier.none.fl_str_mv | 0020-0190 http://hdl.handle.net/10725/4760 http://dx.doi.org/10.1016/j.ipl.2016.07.002 Abu-Khzam, F. N., & Heggernes, P. (2016). Enumerating minimal dominating sets in chordal graphs. Information Processing Letters, 116(12), 739-743. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0020019016301004 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Information Processing Letters |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Enumerating minimal dominating sets in chordal graphs |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_cd0632cfbf58d6c4a363482b027b2df4 |
| identifier_str_mv | 0020-0190 Abu-Khzam, F. N., & Heggernes, P. (2016). Enumerating minimal dominating sets in chordal graphs. Information Processing Letters, 116(12), 739-743. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/4760 |
| publishDate | 2016 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Enumerating minimal dominating sets in chordal graphsAbu-Khzam, Faisal N.Heggernes, PinarThe 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.PublishedN/A2016-11-08T14:05:49Z2016-11-08T14:05:49Z20162016-11-08Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0020-0190http://hdl.handle.net/10725/4760http://dx.doi.org/10.1016/j.ipl.2016.07.002Abu-Khzam, F. N., & Heggernes, P. (2016). Enumerating minimal dominating sets in chordal graphs. Information Processing Letters, 116(12), 739-743.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttp://www.sciencedirect.com/science/article/pii/S0020019016301004enInformation Processing Lettersinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/47602021-03-19T10:00:50Z |
| spellingShingle | Enumerating minimal dominating sets in chordal graphs Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Enumerating minimal dominating sets in chordal graphs |
| title_full | Enumerating minimal dominating sets in chordal graphs |
| title_fullStr | Enumerating minimal dominating sets in chordal graphs |
| title_full_unstemmed | Enumerating minimal dominating sets in chordal graphs |
| title_short | Enumerating minimal dominating sets in chordal graphs |
| title_sort | Enumerating minimal dominating sets in chordal graphs |
| url | http://hdl.handle.net/10725/4760 http://dx.doi.org/10.1016/j.ipl.2016.07.002 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0020019016301004 |