- 學位論文
完全三分圖Ｋ（１，ｍ，ｎ）的IC著色
On the IC-colorings of complete tripartite graphs K(1,m,n)
摘要
令G為一個圖，且f為一個函數，使得G每一個頂點都對應至一個正整數。同時定義f(H)=simf(v),v屬於V(H)，其中H為G的子圖。如果對於每一個正整數k屬於[1,f(G)]，皆存在G的一個連通子圖H，使得f(H)=k，則我們稱f為G的一個IC-著色。很顯然的，對於任意的連通圖G至少存在一個IC著色。圖G的IC-指數,記為M(G),定義為M(G)=max(f(G),f是圖G的ㄧ個IC著色) 。如果f是G的一個IC-著色，使得f(G)=M(G)，則我們稱f為G的一個極大IC著色。在這一篇論文中，我們主要研究完全三分圖的IC-著色，並且證明了M(k(1,m,n))=13*2^(m+n-3)-2^(m-2)+2當2<=m<=n 。
並列摘要
Let G be a graph and let f be a function which maps V(G) into the set of positive integers.We define f(H)=simf(v),v in V(H) for each subgraph H of G.We say f to be an IC-coloring of G if for any integer k in [1,f(G)] there is a connected subgraph H of G such that f(H)=k.Clearly, any connected graph G admits an IC-coloring. The IC -index of a graph G, denoted by M(G) ,is defined to be M(G)=max(f(G),f is a IC-coloring of G).If f is an IC-coloring of G such that f(G)=M(G),then we say that f is an maximal IC-coloring of G. In this thesis, we mainly study the IC-colorings of complete tripartite graphs and prove thatM(k(1,m,n))=13*2^(m+n-3)-2^(m-2)+2 for 2<=m<=n 。