what is a path called that visits every vertex of a graph at least once?

1.1k Views Asked by At

As I understand it, a Hamiltonian path visits every vertex of a graph exactly once. Is there a name for a path which visits every vertex at least once?

Some graphs may be such that a cycle visiting every vertex, must visit some vertices more than once. I'd like to talk about the shortest such cycles.

1

There are 1 best solutions below

0
On

A path doesn't repeat vertices by definition, so any path which does this would be a Hamilton path.

In order to allow vertices to be repeated, you should instead call it a "walk" or "trail" (the difference between the two is whether edges can be used more than once; in a walk they can). I would therefore call this a "covering walk". It seems this terminology has been used before: see this book. However, I would define it if I was going to use it.

An alternative is "spanning walk"; see this paper.