Given N vertices v1,…, vn, how many edges does it take to form a graph that contains a Hamiltonian cycle (v1, v2,…, vN, v1) and a basic binary spanning tree with some vertex vr as root? In this article the question is answered exactly. Moreover, it is shown that for any odd N there exists a natural cycletree with N vertices, a minimal number of edges and a minimal total path length.

In  Information Processing Letters

Publisher  Elsevier
Copyright © 2007 Elsevier B.V. All rights reserved.

Details