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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.