完全二分圖的IC-著色

On the IC-colorings of the complete bipartite graphs

洪綉雯(Shiou-Wen Hong)

指導教授 ： 史青林

中原大學/理學院/應用數學系/碩士(2007年)

https://doi.org/10.6840/cycu200700377

摘要

令G為一個圖，且f為一個函數，使得G中的每一個頂點都對應至一個正整數。同時定義 ，其中H為G的子圖。如果對於每一個正整數 ，皆存在G的一個連通子圖H，使得f (H) = k，則我們稱f為G的一個〝IC-著色〞。很顯然，對於任意的連通圖G至少存在一個〝IC-著色〞。圖G的〝IC-指數〞定義為M (G) = max { f (G) : f為圖G的一個IC-著色}。如果f是G的一個IC-著色，使得f (G)=M (G)，則我們稱f為G的一個〝極大IC-著色〞。在[7]中，E. Salehi等人證明 。在這一篇論文中，我們找出 的IC-指數的上界與下界， 。

關鍵字

極大IC-著色 ； IC-指數 ； IC-著色

並列摘要

Let G be a graph and let f be a function which maps V(G) into the set of positive integers. We define for each subgraph H of G. We say f to be an IC-coloring of G if for any integer 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 an IC- coloring of G }. If f is an IC-coloring of G such that f (G) = M (G), then we say that f is a maximum IC-coloring of G. In [7], E. Salehi et.al. proved that . In this thesis, we find that .

並列關鍵字

IC-coloring ； maximum IC-coloring ； IC-index

參考文獻

[1] R. Alter, J. A. Barnett, “A postage stamp problem”, Amer. Math.

[2] G. Chartrand, Introduction to graph theory, McGraw-Hill Higher Edu-

[4] R. Guy, The Postage Stamp Problem, Unsolved problems in Number

Math. Comput. 69 (2000), pp. 325–337.

Graphs”, Discrete Mathematics, 299(2005), pp. 297–310.