0
$\begingroup$

Suppose I have a connected graph with $n$ vertices and start in some arbitrary vertex $u$. I want to visit every vertex of the graph. I do not care about returning to where I started, and I can visit a node multiple times if needed.

What is the worst possible length of the shortest path, as a function of $n$?

EDIT: The length of a path is here counted simply as the number of times you cross and edge. So we are dealing with unweighted graphs.

$\endgroup$
2
  • 1
    $\begingroup$ That would depend on how long the edges are, right? Or are you measuring length as just the number of edges? I imagine that if the graph is a "star" (one vertex adjacent to each of the other vertices, and no other edges) you get $2n-3$, and I don't see how you can do worse than that. $\endgroup$ Sep 15, 2014 at 13:23
  • $\begingroup$ I was thinking of the unweighted case.I'll edit my post to clarify this. A star was the worst case I could think of as well, but I did not manage to prove any better bound. $\endgroup$
    – Johan
    Sep 15, 2014 at 16:16

2 Answers 2

1
$\begingroup$

To prove that a star is the worst case, it is perhaps best to look at a spanning tree $T$. Choose any leaf $v$. By induction, you can visit all the vertices of $T - v$ in $2(n-1) - 3$ steps. Along the way, you can visit $v$ in two steps. So you can visit all of $T$ in $2(n-1) - 3 + 2 = 2n - 3$ steps.

$\endgroup$
1
$\begingroup$

If $T$ is a spanning tree of your graph $G$, it is easy to see that the shortest walk of $G$ is at worst as big as the shortest walk of $T$. Therefore, the worst possible shortest walks are found on trees.

Say your walk of a tree $T$ has to start from $r$. You can root a given tree arbitrarily, so assign $r$ as the root. Suppose $r$ has at least 2 children.

Let's take the walk corresponding to a depth-first search (DFS) on the tree, starting from $r$. Each time we visit a child vertex in the DFS, we take an edge, and each time we go back to a parent vertex, we take an edge.
Let $v$ be the last vertex visited by the DFS. This vertex $v$ has to be a leaf. Now, for any vertex $w$ that does not lie on the path between $v$ and $r$, the DFS has to come back to the parent of $w$. Therefore each edge except those on the $r-v$ path are visited twice. Since there is at least one such edge, the upper bound for your problem is $2(n - 2) + 1 = 2n - 3$. You can show that this bound is tight with the star tree (which, I think, is the only tree attaining this bound).

$\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.