臺灣博碩士論文加值系統

本論文旨在研究由郵票問題所延伸的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-指數為 .

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 .

中文摘要………………….…………………..….………….Ⅰ
Abstract………………….……………………....………….Ⅱ
誌謝………………….……………………....……...………. Ⅲ
目錄………………….…………………….…………...….... Ⅳ
圖形列表………………….…………………….……..…….Ⅴ
1.緒論………………….…………………….…………….....1
2.預備知識………………….…………………….………....2
2.1預備知識………………….…………………….……...2
2.2已知結果………………….…………………….……...4
3.K(1,1,n)的IC-指數………………….…………………..5
3.1 K(1,1,n)的IC-指數之下界………………….………...5
3.2 K(1,1,n)的IC-指數………………….…………………8
4. 結論………………….…………………….…………….19
參考書目………………….…………………….…………..20


圖形列表
圖1 : 郵票問題… … … … … … … .… … … … … … … … … ..1
圖2 : K(2,2)的一個IC-著色… … … … … … … .… … … … 1

[1]吳森原譯, “圖形論及其應用”, 國立編譯館主編, 1988.
[2]S.G. Penrice, Some new graph labeling problems: A preliminary report, DIMACS
Technical Reports, 95-26(1995), pp. 1-9.
[3] Douglas. B. West(2001), Introduction to Graph Theory, Upper Saddle River,
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.
[5]徐寶根,“關於連通圖的IC-著色”,華東交通大學學報, 23(2006), pp. 134-136
[6] C. L. Shiue and H. L. Fu, The IC-Indices of complete bipartite graphs, Electronic J.
of Combinatorics, 15(2008), #R43.