École Nationale Supérieure de
Techniques Avancées

Résumé

In this report, we study the connected domination number denoted $\lambda_c$ on hypercube graphs and grid graphs. We prove Mujuni's conjecture that $\lambda_c(Q_n)= 2^{n-2}+2$ for small hypercubes $Q_4$ and $Q_5$. We also show the optimal connected domination number on grid graphs of $5$ rows (or columns). We provide four different linear integer formulations for the maximum leaf spanning tree problem that is equivalent to the minimum connected dominating set problem, and eventually report the computational experiments on grid graphs.