Upper bounds on the solution to a directed route inspection problem

Question

If for any strongly connected digraph $D$ we define $\lambda(D)$ to be the length of any shortest closed walk traversing every arc in $D$, then does there exist some constant $m\in\mathbb{R}$ such that $\lambda(D)\leq m|E(D)|$? In addition if no such constant $m$ exists then are there any reasonably simple bounds involving $D$?

---

In the undirected case if $G$ is connected we can construct a multigraph $H=(V(G),E(G)\uplus E(G))$ by parallelly duplicating every edge in $G$ so that by definition the degree of every vertex in $H$ will be even which means $H$ is an Eulerian graph, thus there exists a walk of length $|E(H)|=2|E(G)|$ traversing every edge in $H$ but by definition every walk in $H$ is a walk in $G$ thus $\lambda(G)\leq 2|E(G)|$. Though with that said, I can't seem to construct a similar argument involving parallel arcs for $D$.

Answer 1

No, there is no linear boundary. The smallest boundary you can get is quadratic.

Create a directed graph a follows:

1. $n$ vertices each in the set of lower vertices ($L$) and upper vertices ($U$).
2. Connect the vertices in each set linearly as shown in the picture, with the 'first' vertex in $L$ being $z$ and the 'last' vertex in $U$ being $s$.
3. Connect all vertices of $L$ with all vertices of $U$, direction from $L$ to $U$.
4. Create $k$ detour vertices ($D$), that connect $s$ with $z$ on a long simple path as shown.

This strongly connected digraph $D$ has $|E(D)|=n^2+2n+k-1$ edges (thanks to Ethan for the correction). In a walk covering all edges, between any two edges from $L$ to $U$ you need to take the detour through $D$, so you have at least $k+1$ edges in between. Since there are $n^2$ edges between $L$ and $U$, we have $\lambda (D) \ge (n^2-1)(k+1)$.

If you set $k=n^2$, you get $|E(D)|\sim 2n^2$ and $\lambda (D) \ge n^4-1$, which rules out a linear bound as desired and proves that in any bound of the form

$$\lambda (D) \le c|E(D)|^m$$

we have $m\ge 2$.

OTOH, it's easy to show that

$$\lambda (D) \le 2|E(D)|^2$$

holds: Use the walk of the associated undirected graph, which has, as you proved, length at most $2|E(D)|$, then replace every undirected edge in it with a directed path in $D$ connecting the 2 vertices of the undirected edge in the desired deriction. Such a path can of course not have more than $|E(D)|$ edges, which proves the above inequality.