ZHANG, Yue (2021) The connected domination number of small hypercubes and 5 x n grid PRE - Research Project, ?? - ??.



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.

Item Type:Thesis (PRE - Research Project)
Subjects:Mathematics and Applications
ID Code:8472
Deposited By:Yue ZHANG
Deposited On:13 sept. 2021 15:11
Dernière modification:13 sept. 2021 15:11

Repository Staff Only: item control page