2
$\begingroup$

In a directed graph, a vertex $a$ can reach every vertex, and every vertex can reach another vertex $b$. Can we always sort all the edges as $e_1,e_2,\ldots,e_n$ so that every prefix $e_1,e_2,\dots,e_i$ (when viewed as undirected edges) forms a connected subgraph, and similarly for every suffix $e_i,e_{i+1},\dots,e_n$?

I believe this is true if there is a path from $a$ to $b$ that contains all other vertices. Suppose the path is $a\rightarrow v_1\rightarrow\dots\rightarrow v_k\rightarrow b$. We let the edge $a\rightarrow v_1$ come first, then edges that connect $v_2$ to the set $\{a,v_1\}$ (in any order), then edges that connect $v_3$ to the set $\{a,v_1,v_2\}$, and so on. But is the statement true if there is no path from $a$ to $b$ that contains all other vertices?

$\endgroup$
  • $\begingroup$ to put it in other way, your question is whether a certain sorting of edges has every sub-sorting as the edge set of a connected subgraph. And your argument shows it to be true for directed hamiltonian graphs $\endgroup$ – vidyarthi Mar 2 at 10:39
  • $\begingroup$ I think it is also true for eulerian graphs $\endgroup$ – vidyarthi Mar 2 at 10:42
3
$\begingroup$

Add to $G$ a new edge $e=\vec{ba}$, the new graph $G\cup e$ is strongly connected. Start with a directed cycle containing $e$, let it consist of edges $e_1,e_2,e_3,\dots,e_m,e$, where $e_1$ is incident to $a$ and $e_m$ is incident to $b$. Start with a sequence $e_1,e_2,\dots,e_m$. Now I use an ear decomposition of $G$: the edge set $E$ is a disjoint union of $E_1=\{e_1,e_2,\dots,e_m,e\}$, $E_2$, $E_3$, $\dots,E_s$, where each $E_i$, $i=2,3,\dots,s$ is an ear: it is a set of edges of a simple directed path or cycle $v_1 v_2\ldots v_r$ in which all vertices except $v_1$ and $v_r$ are not covered by the set $F_{i-1}:=E_1\cup\ldots\cup E_{i-1}$ (while $v_1$ and $v_r$ are covered by $F_{i-1}$). The existence of an ear decomposition in a connected directed graph which starts from a given cycle is well known and easy to prove. So your conjecture follows by induction from the following

Lemma. Let $H$ be an undirected graph in which the edges are enumerated by $e_1,\ldots,e_t$ so that for all $i=1,2,\ldots,t$ the graphs formed by $e_1,\ldots,e_i$ and $e_i,\ldots,e_t$ are connected. Assume also that there are vertices $a,b\in V(H)$ such that $a\in e_1,b\in e_t$ and all other vertices of $H$ have degree at least 2. Let $v_1\ldots v_r$ be an ear for $H$, that is, a simple path or cycle with $v_1,v_r\in V(H)$ and $v_2,\ldots,v_{r-1}$ being new vertices. Then the graph $H$ plus this ear also has such an enumeration of edges.

Proof. If $\{v_1,v_r\}\cap \{a,b\}\ne \emptyset$, say $v_r=b$, add the edges $v_1v_2,v_2v_3,\dots,v_{r-1}v_r$ after $e_t$. Otherwise $v_1,v_r$ are not lists of $H$ and each of them is covered at least by two edges. Choose the minimal $i$ for which $e_i$ covers either $v_1$ or $v_r$. Without loss of generality $v_1\in e_i$. Then $i<t$ and $v_r$ is covered by $e_{i+1},\dots,e_t$. Insert the edges $v_1v_2,v_2v_3,\dots,v_{r-1}v_r$ between $e_i$ and $e_{i+1}$.

$\endgroup$

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.