圖的有向路徑覆蓋

Covering Graphs with Directed Paths

謝奇璁(Chi-Tsung Hsieh)

指導教授 ： 傅恆霖

國立交通大學/理學院/應用數學系暨研究所/碩士(2007年)

https://doi.org/10.6842/NCTU.2007.00002

摘要

在這篇論文裡，我們研究完全路徑雙覆蓋的有向形式。一個圖的有向路徑雙覆蓋是在圖的對稱賦向裡的一個有向路徑集合，其中這個圖的對稱賦向裡的每一個邊都要恰好出現在一個路徑裡，而且對圖裡的每一個點而言都會有唯一一條路徑以此點當作起點以及會有唯一一條路徑以此點當作終點。在這篇論文中，首先我們證明了如果一個圖形沒有包含連通部份為點數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.

並列關鍵字

directed path ； symmetric orientation

參考文獻

[2] P. N. Balister. On the Alspach conjecture. Combin., Probability and computing, 10

[3] J. A. Bondy, Small cycle double cover of graphs, in: G. Hahn, G. Sabidussi,

[5] P. K. Chuang, Decomposing Complete Graph into Paths with Prescribed Lengths,

M. Sc. Thesis, National Chiao Tung University, 2003.

[6] F. Harary, Graph Theory, Addison-Wesley, Reading MA, 1972.