2024/11/11 by Andrew Pham, Pham, Andrew
Computer Science · #Advanced Graph Theory Research #Distributed systems and fault tolerance #Cloud Computing and Resource Management
paper · pdf · doi:10.48550/arxiv.2411.07411
Given a simple, finite, nonempty graph G=(V(G),E(G)), a vertex subset D⊆ V(G) is said to be a dominating set if every vertex v∈ V(G)-D is adjacent to a vertex in D. The independent domination number γi(G) is the minimum cardinality among all independent dominating sets of G. Since determining the domination number for general graphs is NP-complete, we focus on the class of k-trees. Favaron established a tight upper bound for 1-trees, while Campos and Wakabayashi determined a tight upper bound for maximal outerplanar graphs, a subclass of 2-trees. We generalize these results and establish a tight upper bound for the independent domination number of k-trees for all k∈ ℕ.