| tags:[ eternal games ]
Disjoint Dominating Sets with a Perfect Matching
(experimental page)
The paper ↗ by William F. Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello study the $DD_m(G)$ and its connection to various graph parameters.
Definitions
- independence number $\alpha(G)$
- dominating set
- domination number $\gamma(G)$
- perfect matching
- eternal eviction model
- (dominating) swap set
- $DD_m(G)$
- weak & strong stem
- weak & strong graph
- (simple) star partitioning
- weight of a partitioning
- $\widehat{G}$ graph
- weak reduction
Results
- For every tree $\gamma(T) = e^\infty_m(T) = DD_m(T) = \alpha(T)$ if and only if $T = \widehat{H}$ for some tree $H$ of order $2|V(T)|$.
- For any tree $T, e^\infty_m(T) = \alpha(T)$ if and only if T has a minimum-weight simple star partitioning containing no $K_1$ parts.
- For $T’$ a week reduction of T, $S(T’) = \frac{1}{2} |V(T)| ⇔ \alpha(T) = S(T)$
- $\alpha(T) = e^\infty_m(T) \Leftrightarrow S(T) = 2|V(T)|$
- Let $p, q \geq 1$. Then $DD_m(K_{1,p} ~\square~ K_{1,q}) = p+q-1$.