(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$.