Premium
On the optional hamiltonian completion problem
Author(s) -
Slater P. J.,
Goodman S. E.,
Hedetniemi S. T.
Publication year - 1976
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230060104
Subject(s) - hamiltonian path , combinatorics , mathematics , graph , hamiltonian (control theory) , hamiltonian path problem , discrete mathematics , computer science , mathematical optimization
The Optional Hamiltonian Completion Problem is defined as follows: let the points V of a graph G be partitioned into a set V 0 of optional points and a set V 1 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 V 1 . This cycle may or may not contain optional points of V 0 . In this paper we present algorithms for solving this problem for trees, unicyclic graphs and cacti.