最佳容錯漢米爾頓及漢米爾頓連接圖

Abstract

當一個k連接漢米爾頓及和米爾頓連接圖損壞k-2及k-3個節點或邊時仍是漢米爾頓及漢米爾頓連接時, 此圖稱為最佳容錯漢米爾頓及漢米爾頓連接圖. 在這篇文章中我們提出一種新的建構方法來建構最佳漢米爾頓及漢米爾頓連接圖.

A k-regular hamiltonian and hamiltonian connected graph G is optimal fault-tolerant hamiltonian and hamiltonian connected if G remains hamiltonian after removing at most k-2 nodes /or edges and remains hamiltonian connected after removing at most k-3 nodes /or edges. In this paper, we investigate a construction scheme to construct optimal fault-tolerant hamiltonian and hamiltonian connected graphs.