Suppose you have a directed graph G = (V,E) with n vertices that is strongly connected (so there is a directed path from every vertex to every other vertex). Consider the length of the shortest closed walk W that visits every vertex. In the worst case, how long can W be?

Here, as usual, by a "closed walk" we mean that we start at some vertex and return to it, and we are allowed to repeat vertices and edges. We measure the length of W by the number of edges, and write it as |W|. Such a walk is sometimes called a "Hamiltonian walk" in the literature.

The answer is floor((n+1)^{2}/4). This simple result was apparently first proved by Yahya Ould Hamidoune, in Proposition 2.1 of his paper published in *Discrete Mathematics* **26** (1979), 227-234. Hamidoune just recently passed away; he was apparently one of Mauritania's most famous mathematicians, and proved many deeper results than the little proposition above. But his graph inequality might prove useful to others, so I reproduce his proof here.

To see the upper bound, let L be a longest simple path in G. (A simple path does not repeat edges or vertices.) Let V-L = { v_{i} : 1 ≤ i ≤ k }. Let v_{0} be the last vertex in L and v_{k+1} be the first vertex in L. Let L_{i} be a simple path from v_{i} to v_{i+1}. Then a Hamiltonian walk W is obtained by following the edges in L_{0}, L_{1}, ..., L_{k}, and then those in L. So the number of edges in W is at most (k+2)|L| = |L|(n+1-|L|). But it is easy to see that r(n+1-r) is maximized when r = ceil(n/2). You can now check that in this case, r(n+1-r) = floor((n+1)^{2}/4), as claimed.

To see that this is best possible, consider a graph where there is a directed chain of floor(n/2) vertices, where the last vertex has a directed edge to ceil(n/2) other vertices, and each of *those* vertices have a single directed edge back to the start of the chain.
The shortest walk covering all the vertices traverses the chain, then an edge to one of the other vertices, then a single edge back, and repeats this ceil(n/2) times. The total length is then (floor(n/2)+1)ceil(n/2) = floor((n+1)^{2}/4). So the bound is tight.

## 2 comments:

Very nice, thanks for posting this. What happens when we ask the same question for an undirected graph?

It's 2(n-1) - use depth-first search, and follow the paths and backedges.

Post a Comment