Article ID: | iaor19971496 |
Country: | Brazil |
Volume: | 5 |
Issue: | 1 |
Start Page Number: | 55 |
End Page Number: | 66 |
Publication Date: | Apr 1995 |
Journal: | Investigacin Operativa |
Authors: | Guimares Gilcina, Netto Paulo Oswaldo Boaventura |
A vertex-set partition in an undirected graph is defined in a way that information given by adjacency relations between the partition sets and internal to them can be used in the study of Hamiltonian problems in the graph. Some results are general and some others are valid only for regular graphs, for which special characteristics allowed the study to obtain interesting particular results. The algorithm uses structural information which allows it to be applied to any graph and the results associated to its use do not depend, either on scope or on validity, on parameter value conditions such as bounds for vertex degrees or vertex degree sums, as it is the case with the Dirac and Bondy-Chvátal theorems.