Minimal dominating sets in interval graphs and trees. (English) Zbl 1350.05121
Summary: We show that interval graphs on \(n\) vertices have at most \(3^{n/3} \approx 1.4422^n\) minimal dominating sets, and that these can be enumerated in time \(O^\ast(3^{n/3})\). As there are examples of interval graphs that actually have \(3^{n/3}\) minimal dominating sets, our bound is tight. We show that the same upper bound holds also for trees, i.e. trees on \(n\) vertices have at most \(3^{n/3}\approx 1.4422^n\) minimal dominating sets. The previous best upper bound on the number of minimal dominating sets in trees was \(1.4656^n\), and there are trees that have \(1.4167^n\) minimal dominating sets. Hence our result narrows this gap. On general graphs there is a larger gap, with \(1.7159^n\) being the best known upper bound, whereas no graph with \(1.5705^n\) or more minimal dominating sets is known.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C05 | Trees |
| 05C30 | Enumeration in graph theory |
References:
| [1] | Brandstädt, A.; Le, V. B.; Spinrad, J., (Graph Classes: A Survey. Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications (1999)) · Zbl 0919.05001 |
| [2] | Byskov, J. M., Enumerating maximal independent sets with applications to graph colouring, Oper. Res. Lett., 32, 547-556 (2004) · Zbl 1052.05055 |
| [3] | Couturier, J.-F.; Heggernes, P.; van ’t Hof, P.; Kratsch, D., Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Theor. Comput. Sci., 487, 82-94 (2013) · Zbl 1283.05200 |
| [4] | Couturier, J.-F.; Heggernes, P.; van ’t Hof, P.; Villanger, Y., Maximum number of minimal feedback vertex sets in chordal graphs and cographs, (Proc. COCOON 2012. Proc. COCOON 2012, LNCS, vol. 7434 (2012)), 133-144 · Zbl 1365.05133 |
| [5] | Couturier, J.-F.; Letourneur, R.; Liedloff, M., On the number of minimal dominating sets on some graph classes, Theor. Comput. Sci., 562, 634-642 (2015) · Zbl 1305.05219 |
| [6] | Eiter, T.; Gottlob, G., Identifying the minimal transversals of a hypergraph and related problems, SIAM J. Comput., 24, 1278-1304 (1995) · Zbl 0842.05070 |
| [7] | Eiter, T.; Gottlob, G.; Makino, K., New results on monotone dualization and generating hypergraph transversals, SIAM J. Computing, 32, 514-537 (2003) · Zbl 1052.68101 |
| [8] | Elbassioni, K.; Makino, K.; Rauf, I., Output-sensitive algorithms for enumerating minimal transversals for some geometric hypergraphs, (Proc. ESA 2009. Proc. ESA 2009, LNCS, vol. 5757 (2009)), 143-154 · Zbl 1256.68150 |
| [9] | Fomin, F. V.; Gaspers, S.; Pyatkin, A. V.; Razgon, I., On the minimum feedback vertex set problem: Exact and enumeration algorithms, Algorithmica, 52, 2, 293-307 (2008) · Zbl 1170.68029 |
| [10] | Fomin, F. V.; Grandoni, F.; Pyatkin, A. V.; Stepanov, A. A., Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications, ACM Trans. Algorithms, 5, 1 (2008), 9:1-9:17 · Zbl 1445.05101 |
| [11] | Fomin, F. V.; Heggernes, P.; Kratsch, D.; Papadopoulos, C.; Villanger, Y., Enumerating minimal subset feedback vertex sets, Algorithmica, 69, 1, 216-231 (2014) · Zbl 1303.05189 |
| [12] | Fomin, F. V.; Kratsch, D., (Exact Exponential Algorithms. Exact Exponential Algorithms, Texts in Theoretical Computer Science (2010), Springer) · Zbl 1370.68002 |
| [13] | Fomin, F. V.; Villanger, Y., Finding induced subgraphs via minimal triangulations, (Proc. STACS 2010 (2010)), 383-394 · Zbl 1230.68108 |
| [14] | Gaspers, S.; Mnich, M., Feedback vertex sets in tournaments, J. Graph Theory, 72, 1, 72-89 (2013) · Zbl 1259.05070 |
| [15] | Golovach, P. A.; Heggernes, P.; Kratsch, D.; Saei, R., An exact algorithm for subset feedback vertex set in chordal graphs, J. Discrete Algorithms, 26, 7-15 (2014) · Zbl 1298.05302 |
| [16] | Golovach, P. A.; Heggernes, P.; Kratsch, D.; Villanger, Y., Generating all minimal edge dominating sets with incremental-polynomial delay, (Proc. ICALP (1) 2013. Proc. ICALP (1) 2013, LNCS, vol. 7965 (2013)), 485-496 · Zbl 1336.05133 |
| [17] | Golumbic, M. C., (Algorithmic Graph Theory and Perfect Graphs. Algorithmic Graph Theory and Perfect Graphs, Annals of Disc. Math., vol. 57 (2004), Elsevier) · Zbl 1050.05002 |
| [18] | (Haynes, T. W.; Hedetniemi, S. T., Domination in Graphs (1998), Marcel Dekker Inc.: Marcel Dekker Inc. New York) · Zbl 0890.05002 |
| [19] | Hujter, M.; Tuza, Z., The number of maximal independent sets in triangle-free graphs, SIAM J. Disc. Math., 6, 284-288 (1993) · Zbl 0779.05025 |
| [20] | Kanté, M. M.; Limouzy, V.; Mary, A.; Nourine, L., Enumeration of minimal dominating sets and variants, (Proc. FCT 2011. Proc. FCT 2011, LNCS, vol. 6914 (2011)), 298-394 · Zbl 1342.05099 |
| [21] | Kanté, M. M.; Limouzy, V.; Mary, A.; Nourine, L., On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets, (Proc. ISAAC 2012. Proc. ISAAC 2012, LNCS, vol. 7676 (2012)), 289-298 · Zbl 1260.05163 |
| [22] | Kanté, M. M.; Limouzy, V.; Mary, A.; Nourine, L., On the enumeration of minimal dominating sets and related notions, SIAM J. Discrete Math., 28, 4, 1916-1929 (2014) · Zbl 1310.05119 |
| [23] | Kanté, M. M.; Limouzy, V.; Mary, A.; Nourine, L.; Uno, T., On the enumeration and counting of minimal dominating sets in interval and permutation graphs, (Proc. ISAAC 2013. Proc. ISAAC 2013, LNCS, vol. 8283 (2013)), 339-349 · Zbl 1407.05222 |
| [24] | Kanté, M. M.; Limouzy, V.; Mary, A.; Nourine, L.; Uno, T., Polynomial delay algorithm for listing minimal edge dominating sets in graphs, (Proc. WADS 2015. Proc. WADS 2015, LNCS, vol. 9214 (2015)), 446-457 · Zbl 1451.68204 |
| [25] | Krzywkowski, M., Trees having many minimal dominating sets, Inform. Proc. Lett., 113, 276-279 (2013) · Zbl 1273.05041 |
| [26] | Moon, J. W.; Moser, L., On cliques in graphs, Israel J. Math., 3, 23-28 (1965) · Zbl 0144.23205 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
