Previous |  Up |  Next


dominating set; antidomatic partition; antidomatic number
A subset $D$ of the vertex set $V(G)$ of a graph $G$ is called dominating in $G$, if for each $x\in V(G)-D$ there exists $y\in D$ adjacent to $x$. An antidomatic partition of $G$ is a partition of $V(G)$, none of whose classes is a dominating set in $G$. The minimum number of classes of an antidomatic partition of $G$ is the number $\bar{d} (G)$ of $G$. Its properties are studied.
[1] Cockayne, E. J., Redetniemi, S. T.: Towards a theory of domination in graphs. Networks 7(1977), 247–261. MR 0483788
[2] Zelinka, B.: Some numerical invariants of graphs. DrSc dissertation, Charles University, Prague 1988 (Czech).
Partner of
EuDML logo