On the number of edges in cycletrees
1996 (English)In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 57, no 4, 225-229 p.Article in journal (Refereed) Published
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 — the answer is approximately . 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.
Place, publisher, year, edition, pages
1996. Vol. 57, no 4, 225-229 p.
data structures, Hamiltonian cycles, traversal of binary trees
Engineering and Technology
IdentifiersURN: urn:nbn:se:uu:diva-27247DOI: 10.1016/0020-0190(95)00183-2OAI: oai:DiVA.org:uu-27247DiVA: diva2:55141