I'm trying to prove the following statement:

Every directed graph $G$ has an independent set $S$ such that any other vertex in G can be reached with a directed path of length $\leq 2$ from a vertex in $S$.

So far, I've tried removing a vertex $v$ from the graph and considering cases where the vertex is in $S$, $A = \{ \text{the set of vertices 1 away from } S \}$ or $B = \{ \text{the set of vertices 2 away from } S \}$. But I'm not getting anywhere.

  • $\begingroup$ $G$ must at least be assumed to be connected, right? $\endgroup$ – M. Winter May 22 '17 at 15:08
  • $\begingroup$ @M.Winter Why would it have to be connected? If you can find $S$ for any connected $G$, you can find an $S_i$ for each component $G_i$ and then $S = \cup_i S_i$. $\endgroup$ – Fabio Somenzi May 22 '17 at 15:12
  • $\begingroup$ @FabioSomenzi Right! Of course $\endgroup$ – M. Winter May 22 '17 at 15:14

In the situation where $G$ is undirected, any maximal independent set $S$ has this property. If $v$ is distance at least $2$ from $S$ then $S \cup \{v\}$ is independent and larger than $S$.

In the directed situation, this motivates you to take a maximal independent set $S$ as the starting point. We then proceed by induction on the number of vertices (the base case(s) are easy). Recall that in the underlying undirected graph, all vertices are distance at most $1$ from a maximal independent set.

Given $v \in V(G) \setminus S$ either there is an edge $S \to v$ (which is good). Or all the edges point $v \to S$ (bad). Throw together these bad vertices in the set $T$. By induction, we can choose an independent set $T'$ in $T$ with the desired property (for the subgraph induced by $T$). Let $U$ be the set of $u \in S$ such that there is an edge $v \to u$ with $v \in T'$.

Now let $S' = S \setminus U \cup T'$. Then first of all, $S'$ is idependent.

Let $a, b \in S'$. If $a, b \in S$ then $a, b$ have no edges between them by independence of $S$. If $a \in S$ but $b \notin S$ (or vice versa) then there are no edges between $a$ and $b$ by definition of $T$ and $U$. Otherwise $a, b \in T'$ and again there are no edges between them by independence of $T'$.

Does $S'$ satisfy the conditions?

Let $w \in V(G)$. If $w \in S'$ we are done. Next, if $w$ is not in $S'$ and not in $T$ then there is an edge $u \to w$ with $u \in S$. If $u \in U$ then there is a path $v \to u \to w$ with $v \in T'$. Otherwise, $u \in S'$ and $u \to w$ is a path $S' \longrightarrow w$ of length $1$. Finally, if none of the above happen then $w \in T \setminus T'$ and, by definition of $T'$, there is a path $T' \longrightarrow w$ of length $\le 2$. In all cases, there is a path $S' \longrightarrow w$ of length $\le 2$.

  • 1
    $\begingroup$ How would this work for the following case? Let $V = \{a,b,c\}$ and $E = \{(b,a),(b,c),(c,a),(c,b)\}$. Let $S=\{a\}$ be the initial maximal independent set of the underlying undirected graph. Then $T' = U = \emptyset$, if I'm not mistaken, and $S' = S$, which is not a solution. $\endgroup$ – Fabio Somenzi May 22 '17 at 16:16
  • $\begingroup$ Right, if there is a cycle in $T$ the solution breaks down. It should be possible to fix the solution. Let me think some more. $\endgroup$ – Trevor Gunn May 22 '17 at 16:29
  • $\begingroup$ Thanks. In your definition, it seems that $T$ and $S$ may overlap. Is that interpretation correct? $\endgroup$ – Fabio Somenzi May 22 '17 at 16:51
  • $\begingroup$ As I was trying to fix this, I realized I would be do the construction recursively. This suggests to use induction. Hopefully with this new idea, the construction is correct. $\endgroup$ – Trevor Gunn May 22 '17 at 17:26
  • 2
    $\begingroup$ It looks OK now. A couple of comments. (1) When it says "Let $v \in V(G) \setminus S'$. If $w \in S'$ we are done." The two conditions are mutually exclusive. Maybe, reverse the order? (2) A vertex in $V(G) \setminus S'$ may be one not in $S \cup T$, but reachable in one step from $U$. Such a vertex is OK, because it's reachable in two steps from some vertex in $T'$, but it may be worth pointing it out. (If it weren't for such vertices, the condition on $S$ could be tightened.) $\endgroup$ – Fabio Somenzi May 22 '17 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.