On finding hamiltonian cycles or paths in certain graphs and related NP - complete problems

摘要

A graph G is in the set F{n, k,m) of graphs if G is a k - connected graph of order n such that max{d(u),d(v)} ≥ m for each pair of vertices u and v with distance two. In Fan proved that every graph G in F(n, 2, n/2) is hamiltonian. In this note for each graph G in F{n, 2, n/2) a polynomial time algorithm for finding a hamiltonian cycle in G is presented. A similar result on the traceability of the graph H in F{n, 1, (n ― l)/2) and a polynomial time algorithm for finding a hamiltonian path in the graph H are obtained. Moreover, Fan's theorem is further generalized and related NP - complete problems are presented.