cstheory 에서이 질문에 대답하면서 나는 (비공식적으로) 다음 정리를 즉석에서 증명했습니다.

정리 : 고정 경우 해밀턴 사이클 프로브는 길이 ≤ l 사이클을 포함하지 않는 최대 3 도의 평면 2 분자 무 방향 그래프로 제한 되더라도 NP- 완료 상태를 유지합니다 .l≥3

$l \geq 3$≤l

$\leq l$

아직 어딘가에 나타나지 않은 것 같습니다.
그러나 “SGS에 알 수 없음”으로 표시된 graphclasses.org에서 많은 Hamiltonian주기 / 경로 문제를 해결할 수 있습니다 (예 : 이 항목 참조 ). 실제로 직접 추론는 해밀 토니안 사이클 경로 문제는 여전히 제한 경우 NP 완전하다는 것이다 그래프, 여기서 각각 H 저는 적어도 하나의주기를 포함한다.(H1,...,Hk)-free

$(H_1,...,H_k)\text{-free}$Hi

$H_i$

종이 / 책이 ​​어디에서 참조되었는지 알려주시겠습니까?

(그래서 graphclasses.org에서 사람들에게 연락 할 것입니다)

답변