連結網路上之漢彌爾頓性質

Abstract

在這篇論文當中，我們研究了一些漢彌爾頓問題，像是相互獨立漢彌爾頓以及泛可放置漢彌爾頓。在圖G中，我們用n來標記頂點的數目並用e來標記邊的數目。我們用 來標記G的補圖中邊的數目。假設G為一圖並e<=n-4且n>=4。我們證明除了n=5且e=1的情形之外，在G中任一對不同的頂點之間有至少n-2- 條相互獨立漢彌爾頓路徑。假設G任兩不相鄰點的分支度和至少n+2。令u和v為G的任兩相異點。我們證明若(u,v) in E(G)，則u和v之間有至少degG(u) + degG(v) - n條相互獨立漢彌爾頓路徑且其他情形下，u和v之間有至少degG(u) + degG(v)–n+2條相互獨立漢彌爾頓路徑。

排列圖An,k為星狀圖的一般化。它比星狀圖在大小上更為彈性。已有些研究著重在排列圖的漢彌爾頓性與泛圈性。我們提出新的概念稱為泛可放置漢彌爾頓。一漢彌爾頓圖G為泛可放置若對G中任兩相異點x和y，以及對任意整數l滿足d(x,y)≦l≦|V(G)|-d(x,y)，G存在一漢彌爾頓圈C使得x和y在C上的距離為l。一圖G為泛連通圖若存在一條長為l之路徑連接兩相異點x和y且d(x,y)≦l≦|V(G)|-1。我們證明An,k 為泛可放置漢彌爾頓且泛連通若k≧1且n-k≧2。

假設m和n為正偶數且n>=4。已知每個蜂巢矩形圓環面HReT(m,n)為三正則二分圖。我們證明在任何HReT(m,n)中，存在三條內部不相交衍生路徑連接x和y，當x和y分屬不同的分割集合。對任意一對x和y屬於同一分割集合，存在一頂點z在沒有x和y的分割集合中，使得G-{z}中存在有三條內部不相交衍生路徑連接x和y。對任三點x，y和z屬於同一分割集合，G-{z}中存在有三條內部不相交衍生路徑連接x和y，若且唯若n>=6或m=2。

In this thesis, we study some variant of hamiltonian problems, such as mutually independent hamiltonicity and panpositionable hamiltonicity. We use n to denote the number of vertices and use e to denote the number of edges in graph G. We use e to denote the number of edges in the complement of G. Suppose that G is a graph with e<=n-4 and n>=4. We prove that there are at least n-2-e mutually independent hamiltonian paths between any pair of distinct vertices of G except n=5 and e=1. Assume that G is a graph with the degree sum of any two non-adjacent vertices being at least n+2. Let u and v be any two distinct vertices of G. We prove that there are degG(u) + degG(v) - n mutually independent hamiltonian paths between u and v if (u,v) in E(G) and there are degG(u) + degG(v) -n + 2 mutually independent hamiltonian paths between u and v if otherwise.

The arrangement graph An,k is a generalization of the star graph. It is more flexible in its size than the star graph. There are some results concerning hamiltonicity and pancyclicity of the arrangement graphs. We propose a new concept called panpositionable hamiltonicity. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and for any integer l satisfying d(x,y)≦l≦|V(G)|-d(x,y), there exists a hamiltonian cycle C of G such that the relative distance between x and y on C is l. A graph G is panconnected if there exists a path of length l joining any two different vertices x and y with d(x,y)≦l≦|V(G)|-1. We show that An,k is panpositionable hamiltonian and panconnected if k≧1 and n-k≧2.

Assume that m and n are positive even integers with n□4. It is known that every honeycomb rectangular torus HReT(m,n) is a 3-regular bipartite graph. We prove that in any HReT(m,n), there exist three internally-disjoint spanning paths joining x and y whenever x and y belong to different partite sets. For any pair of vertices x and y in the same partite set, there exists a vertex z in the partite set not containing x and y, such that there exist three internally-disjoint spanning paths of G-{z} joining x and y. For any three vertices x, y, and z of the same partite set there exist three internally-disjoint spanning paths of G-{z} joining x and y if and only if n>=6 or m=2.