Distance domination in vertex-partitioned graphs
MTA R\'enyi Institute \& University of Pannonia
Minisymposium: GRAPH DOMINATION
Content: We consider a variation of the graph domination problem, which involves two positive integer parameters $k$ and $d$. Given a connected graph $G$ and a partition $(V_1,\dots,V_k)$ of its vertex set $V(G)$, the task is to find subsets $D_1,\dots,D_k$ of $V(G)$ such that for each $v\in V_i$ there is a vertex $v'\in D_i$ whose distance from $v$ is at most $d$. One of the problems is to determine a general upper bound of the form $|D_1|+\ldots+|D_k|\le c\cdot|V(G)|$. \medskip This is joint work with Allan Frendrup and Preben Dahl Vestergaard.