domination number
- https://mathworld.wolfram.com/DominationNumber.html
- domination number – The domination number $\gamma(G)$ of a graph $G$ is the minimum size of a dominating set of vertices in $G$ …
- unknown
- maximum independent set $k$ upper bounds domination number by $\mathcal O(k)$ – Every maximal independent set is also a dominating set because any undominated vertex could be added to the independent set.
- domination number $k$ upper bounds diameter by $\mathcal O(k)$ – An unbounded diameter implies a long path where no vertices that are more than $3$ apart may be dominated by the same dominating vertex, otherwise we could shorten the path. Hence, the number of dominating vertices is also unbounded.
- bounded cluster does not imply bounded domination number
- bounded edgeless does not imply bounded domination number
- SchroderThesis
- page 15 : bounded vertex cover does not imply bounded domination number – Proposition 3.5
- https://mathworld.wolfram.com/DomaticNumber.html
- domination number – The maximum number of disjoint dominating sets in a domatic partition of a graph $G$ is called its domatic number $d(G)$.