Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.07411 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912722535317504 |
|---|---|
| author | Pham, Andrew |
| author_facet | Pham, Andrew |
| contents | Given a simple, finite, nonempty graph $G=(V(G),E(G))$, a vertex subset $D\subseteq V(G)$ is said to be a dominating set if every vertex $v\in 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\in \mathbb{N}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07411 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Independent Domination of k-Trees Pham, Andrew Combinatorics Given a simple, finite, nonempty graph $G=(V(G),E(G))$, a vertex subset $D\subseteq V(G)$ is said to be a dominating set if every vertex $v\in 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\in \mathbb{N}$. |
| title | Independent Domination of k-Trees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.07411 |