2024/03/01 by Felicity Bryant, Bryant, Felicity, Elena Pavelescu +1 · 1 citation
Computer Science · Mathematics · #05C10 #57M15 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Geometric Topology (math.GT) #Mathematics and Applications
paper · pdf · doi:10.48550/arxiv.2403.00595
openalex publication_date 2024/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set of vertices of a graph G such that each vertex of G is either in the set or is adjacent to a vertex in the set is called a dominating set of G. If additionally, the set of vertices induces a connected subgraph of G then the set is a connected dominating set of G. The domination number γ(G) of G is the smallest number of vertices in a dominating set of G, and the connected domination number γc(G) of G is the smallest number of vertices in a connected dominating set of G. We find the connected domination numbers for all triangulations of up to thirteen vertices. For n≥ 15, n≡ 0 (mod 3), we find graphs of order n and γc=(n)/(3). We also show that the difference γc(G)-γ(G) can be arbitrarily large.