TransWikia.com

(Weakly) connected sets with large (out-)boundary

MathOverflow Asked on February 15, 2021

Let $Gamma=(V,E)$ be a connected undirected graph with n vertices such that every vertex has degree at least $4$. Now draw arrows on some of the edges, in such a way that the in-degree of every vertex is $geq 2$. It is allowed to draw arrows on both directions on an edge.

Must there be a connected subset $V’subset V$ (that is, $Gamma_{V’}$ is connected, as an undirected graph) having at least $delta n$ elements in its outboundary?

(Feel free to define the outboundary of $V’$ either as the set of all $w$ not in $V’$ such that there exists an arrow from some vertex in $V’$ to $w$, or as the set of all $w$ in $V’$ such that there exists an arrow from $w$ to some vertex not in $V’$.)

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP