3－正则3－连通无爪平面图的Hamilton圈问题和Hamilton路问题的NP－完全性

NP-Completeness of Hamilton Circuit Problem and Hamilton Path Problem for 3-Regular 3-Connected Claw-Free Planar Graphs

本文证明了既使对３－正则３－连通无爪平面图，Ｈａｍｉｌｔｏｎ圈（路）问题也是ＮＰ－完全的．

This paper shows that Hamilton circuit (path) problem is NP-complete even for 3-regular 3-connected claw-free planar graphs.