Abstract

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.