On the optional hamiltonian completion problem
Peter J. Slater, S. E. Goodman, Stephen T. Hedetniemi · Networks · 1976
Abstract The Optional Hamiltonian Completion Problem is defined as follows: let the points V of a graph G be partitioned into a set V0 of optional points and a set V1 of non‐optional points; determine the minimum number of new lines which when added to G result in a graph which has a cycle containing every point of V1. This cycle may or may not contain optional points of V0. In this paper we present algorithms for solving this problem for trees, unicyclic graphs and cacti.