互斥路徑的蘭西數

Abstract

在討論蘭西數R(G)時，先給一個圖形G，然後我們可以從一個完全圖中，任意塗兩個顏色在這個圖的邊上，如果不管怎麼塗色都確定可以從中得到一個同色的子圖，而且它同構於圖形G，那我們就從那些符合的圖裡面找到一個最小的完全圖Kr，同時就把蘭西數R(G)定義為r。在這一篇論文中，我們將會呈現一些蘭西數的結果，就是當 n 介於2到7之間外加所有的偶數，而 m 是任意數時，我們都可以確定R(mPn)=m(n+[n/2])-1。

For a fixed graph $G$, we define the smallest integer $r=R(G)$ to be the order of a complete graph $K_{r}$ such that no matter how we assign two colors to the edges of $K_{r}$, there exists a monochromatic subgraph which is isomorphic to $G$. In this thesis, we show that for $2 \leq n \leq 7$, $R(mP_{n})=m(n+[n/2])-1$ for any $m$.