8
$\begingroup$

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2)

Let $T$ be a tree and $r, m$ non-negative integers. Place up to $rm$ pebbles on the vertices of $T$ (each vertex may get zero, one or more pebbles). Then there exists a set $S \subseteq V(T)$ of at most $m-1$ vertices of $T$ such that the number of pebbles in any component of $T - S$ does not exceed $r$.

Now, graphs of bounded tree-width share the separation properties of trees to a certain extent, and indeed one can use the above statement for trees to derive the following

Let $G$ be a graph of tree-width at most $k$, let $r, m$ be two integers. Place up to $rm$ pebbles on the vertices of $G$. Then there exists a set $X \subseteq V(G)$ of at most $(k+1)(m-1)$ vertices such that the number of pebbles in any component of $G - X$ does not exceed $r$.

(This is certainly well-known, but I can't find a reference right now. If you have one, please let me know!)

proof: Let $(T, \mathcal{V})$ be a tree-decomposition of $G$ of width at most $k$. For every $v \in V(G)$, the tree-nodes $t \in T$ with $v \in V_t$ form a subtree of $T$, which we denote by $T_v$. Fix a root for $T$, thus orienting $T$. Every $T_v$ now also has a root $r_v$, the vertex of $T_v$ which is minimal in the tree-order. For every $v \in V(G)$, place the number of pebbles it carries on the vertex $r_v \in T$.

By the above assertion for trees, we find $S \subseteq V(T)$ of size at most $m-1$ such that no component of $T-S$ has more than $r$ pebbles. Let $X := \bigcup_{s \in S} V_s$ be the union of the bags whose tree-nodes lie in $S$. Clearly $|X| \leq (k+1)|S| \leq (k+1)(m-1)$. Let $C$ be a component of $G-X$. Then all the the vertices of $C$ lie in bags of the same component $D$ of $T-S$. The number of pebbles on $C$ is at most the number of pebbles on $D$: For every $v \in C$, the root $r_v$ must lie in $D$ or below $D$. If it is in $D$, then $r_v$ carries the same number of pebbles as $v$. If not, then there exists some $s \in S$ separating $r_v$ from $D$; but then $s \in T_v$ and in fact $v \in X$, contrary to assumption. $\square$

What I find unsatisfactory about this generalisation, though, is that the case $k=1$ does not reduce to the statement about trees, since we have a $(k+1)$ instead of a $k$. I do not see a way how to get rid of the +1 in general, but also could not find an example where the bound is sharp. Can the bound above be improved so as to specialise to the tree-case when $k=1$?

To wrap it all up, my question is: Let $f(k,m)$ be the minimum integer such that whenever $\leq rm$ pebbles are placed on a graph of tree width at most $k$ ($r$ integer), there exists a set $X$ of at most $f(k,m)$ vertices such that no component of $G-X$ has more than $r$ pebbles. Can you determine $f(k,m)$ precisely?

Thank you very much in advance!

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.