On the number of edges in cycletrees

Margus Veanes and Jonas Barklund

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.

Details

Publication typeArticle
Published inInformation Processing Letters
URLhttp://dx.doi.org/10.1016/0020-0190(95)00183-2
Pages225-229
Volume57
PublisherElsevier
> Publications > On the number of edges in cycletrees