MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a question about the number of different ways to separate a terminal vertex from labeled vertex sets in a simple graph. There is a bound on this number that I am interested in. I have succeeded in proving a suitable upper bound, and am now wondering whether any research on similar topics has been done before; it would be nice if I could refer to some source for the claimed bound rather than proving it from scratch. Here are the details.

Let $G$ be a finite simple connected undirected graph with some distinguished terminal vertex $t$.Let $X$ be a finite set of labels; each vertex in $V(G) \setminus \{t\}$ can be labeled with arbitrarily many labels from the set $X$, which we represent by a labelling function $f : V(G) \setminus \{t\} \to 2^X$ which maps to a vertex $v$ the set of labels $f(v)$ that the vertex has. Consider a subset of vertices $S \subseteq V(G) \setminus \{t\}$, and call this a separator. Let $G - S$ denote the graph $G$ after removing all vertices of $S$. We say that $S$ separates the terminal $t$ from a label $x \in X$ if there is no path in $G - S$ from $t$ to a vertex with label $x$, i.e. a vertex $v$ with $x \in f(v)$. The set of labels separated by $S$ is then simply the set of all labels $x \in X$ for which $S$ separates $t$ from $x$.

Now fix some integer $c > 0$, and look at the different label sets which are separated from t by a size-c separator: $C_c :=$ { $X' \subseteq X$ | there is a separator $S$ of size $c$ which separates $X'$ from $t$}

Now my claim is that $|C_c| \leq |X|^{(g(c))}$ for some appropriate function $g$, or equivalently that for fixed separator size $c$ the number of different ways to separate $t$ from the labels is polynomial in the number of labels. Is this known? Has there been any work related to this, or is there a reference I can quote for such a bound? Any insights are much appreciated.

share|cite|improve this question
For what it's worth, your definition is fairly complex and not super-closely related to anything I have seen before, so it would be surprising if these notions have been studied, in my opinion. If there is any chance it exists, you could try looking in the literature on multi-way cuts or multicuts. – Dave Pritchard Dec 13 '10 at 16:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.