Transition coverage for a DFA
This is related to a well known problem with a conjecture due to Karpovsky and Moskalev [1] (I still believe is open) that at most V-1 paths are needed.  It is tied to conjector of Erdos, Goodman, and Posa [2].

If you want the state of the art today, I suggest doing a thorough reverse-citation search on [1].



[1] Karpovsky, M. G., and E. A. Moskalev. "Covering of edges of graph by a minimal set of paths." Discr. Math 58.2 (1986): 214. (This is in the "research problems" section)

[2] Erdos, Paul, Adolph W. Goodman, and Louis Pósa. "The representation of a graph by set intersections." Canad. J. Math 18.106-112 (1966): 86.