完全三分圖K(2,2,n)的IC-著色研究

A Study of IC-coloring of K(2,2,n)

石雅郡(Ya-Chum Shih)

指導教授 ： 劉立民教授

中原大學/理學院/應用數學研究所/碩士(2010年)

https://doi.org/10.6840/cycu201000163

摘要

令G為一連通圖，V=V(G)為圖G的頂點集，且f:V→N為一函數，而圖G中的子圖H，定義為fs(H)=，再者我們將fs(G)記為S(f)。如果對任意正整數k在[1,S(f)],，均可以找到一個圖G中的連通子圖H，使得fs(H)=k，那麼我們就稱f為圖G的一個IC-著色。同時，M(G)=max﹛S(f):f為圖G的一個IC-著色﹜，則稱M(G)為圖G的IC-指數，若f為圖G的一個IC-著色且fs(G)=M(G)，則稱f為圖G的一個極大IC-著色。在這一篇論文中，我們找出了K(2,2,n)的IC-指數上界與下界， 。

關鍵字

IC-著色 ； IC-指數

並列摘要

Let G be a connected garph. V=V(G) is a vertexes set of G, f:V→ N is a coloring function and fot any subgraph H G, we define fs(H)= and denote fs(G)=S(f). The function is called an IC-coloring of G if for and k in the set [1,S(f)], there exist an induced connected subgraph H of G, such that fs(H)=k. The IC-index of graph G, denoted byM(G), is defined to be M(G)=max﹛S(f):f is an IC-coloring of G﹜. We say f is a maximal IC-coloring of G if f is an IC-coloring of G with fs(G)=M(G). In this thesis, we find the lower bound and upper bound of the IC-index of K(2,2,n) is 。

並列關鍵字

IC-index ； IC-coloring

參考文獻

［3］張敏南，完全三分圖K(1,m,n)的IC-著色研究，中原碩士論文，2009。

［8］王薪婷，完全三分圖K(1,1,n)的IC-著色與IC-指數，中原碩士論文，2009。

［1］徐保根，“關於連通圖的IC-著色”，華東交通大學學報，23(2006),134-136。

［2］吳森原譯，“圖形論及其應用”，國立編譯館主編，1988。

［4］S.G Penrice, Some new graph labeling problems: a preliminary report,DIMACS Tech. Rep. 95-26(1995),1-9。