A Note on the Maximum Number of Minimal Connected Dominating Sets in a Graph

2021/11/10 by Faisal N. Abu-Khzam, Abu-Khzam, Faisal N.
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2111.06026

openalex publication_date 2021/11/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove constructively that the maximum possible number of minimal connected dominating sets in a connected undirected graph of order n is in Ω(1.489ⁿ). This improves the previously known lower bound of Ω(1.4422ⁿ) and reduces the gap between lower and upper bounds for input-sensitive enumeration of minimal connected dominating sets in general graphs as well as some special graph classes.

Related

• Maximum Number of Minimum Dominating and Minimum Total Dominating Sets
• Below all subsets for Minimal Connected Dominating Set
• Bounds on the Maximum Number of Minimum Dominating Sets
• On the maximum number of minimal connected dominating sets in convex bipartite graphs
• The maximum number of connected sets in regular graphs