完全三分圖K(1,1,n)的IC-著色與IC-指數

The IC-coloring and the IC-index of K(1,1,n)

王薪婷(Cin-dy Wang)

指導教授 ： 劉立民

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

https://doi.org/10.6840/cycu200900750

摘要

本論文旨在研究由郵票問題所延伸的IC-著色問題. 令G是一個連通圖, 且f是從圖G頂點集V(G)映至正整數的集合N的函數；對於每個圖G中的連通子圖H, 我們定義fs(H)=. 如果對每一個正整數k在[1,S(f)], 都存在一個圖G的連通子圖H, 使得fs(H)=k, 那麼f就稱為圖G的一個IC-著色. 如果M(G)=max{fs(G):f為為圖 的一個IC-著色}, 則稱M(G)為圖G的IC-指數. 若f為圖G的IC-著色且fs(G)=M(G), 則稱f為圖G的一個極大IC-著色. 在這一篇論文中, 我們先找到K(1111n)的IC-指數之下界, 進而證明K(1,1,n)的IC-指數為 .

關鍵字

IC-指數 ； IC-著色

並列摘要

We extend the idea of stamp problem to IC-coloring and study it. Let G be a connected graph and let . For each connected subgraph H of G; we define . If for each integer , there is a connected subgraph H of G such that , then f is called an IC-coloring of G. The IC-index of a graph G, denoted by M(G), is defined to be M(G) : 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 . In this thesis, we find the lower bounds of the IC-index of K(1,1,n) and then prove that the IC-index of K(1,1,n) is .

並列關鍵字

IC-coloring ； IC-index

參考文獻

Technical Reports, 95-26(1995), pp. 1-9.

NJ07458: Prentice Hall.

[4] E. Salehi, S. Lee and M. Khatirinejad, IC-Colorings and IC-Indices of graphs,

Discrete Mathematics, 299(2005), pp. 297-310.

[6] C. L. Shiue and H. L. Fu, The IC-Indices of complete bipartite graphs, Electronic J.