三正則及連通圖中漢米爾頓性質之連線需求數目的研究

Abstract

給一個圖G=(V,E)以及邊集合R屬於E，其中R的邊為獨立路徑。如果一個圖G包含漢米爾頓迴路以及含有任何的需求邊R且|R|小於等於k，則圖G稱為k-漢米爾頓需求邊。我們定義圖G的漢米爾頓需求邊且k為最大時，稱為hr(G)。如果一個圖G-F包含漢米爾頓但不包含壞邊F且|F|小於等於k，則圖G稱為k-漢米爾頓容錯邊。我們定義圖G的漢米爾頓容錯邊且k為最大時，稱為hf(G)。在這篇論文中，我們要證明如果圖G為三正則漢米爾頓圖，則hf(G)小於等於1。如果圖G為三正則漢米爾頓圖且hf(G)=1，則hr(G)大於等於1且hr(G)小於等於3。我們將介紹一些hf(G)=1且hr(G)=i其中i=1,2,3的3-連通漢米爾圖G，以及一些hf(G)=0且hr(G)=1的3-連通漢米爾圖G。

Given a graph G = (V,E) and edge set R belong E, where the edges of R form independent paths. A graph G is k-edge-required-hamiltonian if it contains a hamiltonian cycle including any R whenever |R| <= k. We define edge-required hamiltonicity of G, denoted by hr(G), to be the maximum of such k. A graph G is k-edge-fault-tolerant-hamiltonian if G–F is hamiltonian for any faulty edge set F with |F| <= k. We define edge-fault-tolerant hamiltonicity of G, denoted by hf(G), to be the maximum of such k. In this thesis, we prove that hf(G) <= 1 if G is a cubic hamiltonian graph, 1 <= hr(G) <= 3 if G is a cubic hamiltonian graph with hf (G) = 1. We present some cubic 3-connected hamiltonian graphs G with hf(G) = 1 and hr(G) = i for i = 1, 2, 3, a cubic 3-connected hamiltonian graph G with hf(G) = 0 and hr(G) = 0, and a cubic 3-connected hamiltonian graph G with hf(G) = 0 and hr(G) = 1.