圖的有向路徑覆蓋

Abstract

在這篇論文裡，我們研究完全路徑雙覆蓋的有向形式。一個圖的有向路徑雙覆蓋是在圖的對稱賦向裡的一個有向路徑集合，其中這個圖的對稱賦向裡的每一個邊都要恰好出現在一個路徑裡，而且對圖裡的每一個點而言都會有唯一一條路徑以此點當作起點以及會有唯一一條路徑以此點當作終點。在這篇論文中，首先我們證明了如果一個圖形沒有包含連通部份為點數3 的完全圖且為3 退化圖則這個圖就存在有向路徑雙覆蓋。再來我們也找出了完全二分圖Kn,n與完全多分圖Km(n)(n為奇數,m≠3,5)的有向路徑雙覆蓋。

In this thesis we study an oriented version of perfect path double cover (PPDC). An oriented perfect path double cover (OPPDC) of a graph G is a collection of oriented paths in the symmetric orientation S(G) of G such that each edge of S(G) lies in exactly one of the paths and for each vertex v ∈ V (G) there is a unique path which begins in v (and thus the same holds also for terminal vertices of the paths). First we show that if G has no components which isomorphism to K3 and G is a 3-degenerate graph, then G has an OPPDC. Next we also construct an OPPDC for complete bipartite graph Kn,n and multipartite graph Km(n) (n is odd and m ≠ 3, 5),respectively.