3
$\begingroup$

We have a graph $G$ with binary values on it's vertices. If we flip the value of an vertex $v$ $ \forall v \in V(G)$ (that is, from $o_v$ in $\neg o_v$, where $o$ is the value of the vertex $v$). And the values of it's neighbors will flip as well, so the value of $w$, $\forall w \in N_G(v)$ will flip from $o_w$ in $\neg o_w$.

The interesting property to this type of graph is that if all the vertices have the same value $o$, then there exists a set $S$ that if the flip the vertices in $S$, one at a time (no matter the order), then all the vertices in the graph will have the same value $\neg o$.

By $m(v, X)$ we denote the number of edges from the vertex $v \in V(G)$ to > the subset $X \subseteq V(G)$

List the proprietes of $m(v, S)$ and $S$ ($\forall v \in V(G)$).

My try:

There are 2 cases for this problem. If the graph $G$ is a connected graph then we need to flip only one node to get from $o$ to $\neg o$. And $|S| = 1$ and $S$ can be made from any node in the graph. Also, because of this $m(v, S) \in \{0, 1\}$.

If the graph is not connected, it will be partitioned in $k$ connected partitions. This means that $|S| = k$, $S$ will have only one node from each partition.

How will you approach this problem?

$\endgroup$
  • $\begingroup$ The problem doesn't seem to be well specified. Suppose the graph is a path on vertices $a$, $b$ and $c$. I decide to flip $a$, so $b$ gets flipped. You seem to be assuming that, then, $c$ gets flipped because $b$ did. If that's the case, why doesn't $a$ get flipped back, since $a$ is also a neighbour of $b$. You should ask for clarification from the person who set you the exercise. $\endgroup$ – David Richerby Nov 13 '16 at 20:24
  • $\begingroup$ But, even if the question can be clarified, we discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Is there some specific conceptual issue you're uncertain about? Good conceptual questions are usually useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Nov 13 '16 at 20:25
  • $\begingroup$ I have no idea what you're asking. Might be a language issue. $\endgroup$ – Yuval Filmus Nov 14 '16 at 8:25

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.