平面圖的點變樹分割及漢彌頓圈問題

Abstract

一個圖Ｇ的點集合，最少可被分割成的部份集合個數，使得每個部份集合 皆各自衍生出一個不含圈的子圖，稱為圖Ｇ的點分割數，並表示為ａ(Ｇ) 。在本論文中，我們介紹另一個點分割數的變形，稱為點變樹分割數，並 表示為ａ＿ｔ(Ｇ)；它是一個圖Ｇ的點集合，最少可被分割成的部份集合 個數，使得每個部份集合各自衍生出的子圖都是一棵樹。我們證明：如果 圖Ｇ是一個連通平面圖，則圖Ｇ有漢彌頓圈的充要條件是圖Ｇ的平面對偶 圖Ｇ^*之點變樹分割數ａ＿ｔ(Ｇ^*)為２，並且我們證明：如果圖Ｇ是一 個最大平面圖，則ａ(Ｇ)＝１若且唯若ａ＿ｔ(Ｇ)＝１，ａ(Ｇ)＝２若且 唯若ａ＿ｔ(Ｇ)＝２與ａ(Ｇ)＝３若且唯若ａ＿ｔ(Ｇ)≧３。我們也研究 在最大平面圖中找漢彌頓圈之問題，而且針對最大平面圖提出一個有用的 檢查方法，藉以判斷某些最大平面圖是沒有漢彌頓圈的。 The vertex arboricity a(G) of a graph G is defined to be the minimum number of subsets into which the vertices of G can be partitioned such that each subset induces an acyclic graph. In this thesis, we introduce a variant of vertex arboricity, called vertex-to=tree arboricity a_t(G); it is the minimum number of subsets into which the vertices of a graph G can be partitioned so that each subset induces a tree. We prove that if G is a connected planar graph then G is Hamiltonian if and only if a_t(G^*)=2, and we prove that if G is a maximal planar graph, then a(G)=1 iff a_t(G)=1, a(G)=2 iff a_t(G)=2, and a( G)=3 iff a_t(G)≧3. We also investigate the Hamiltonian cycle problem for maximal planar graphs and propose a useful method checking non-Hamiltonian maximal planar graphs.