臺灣博碩士論文加值系統

令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 。

Contents

中文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . . . . . . I
Abstract . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . . . . .. II
謝誌. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . . . . ..III
Contents. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . ..IV
List of Figures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . .. . . . . ...V
1 Introduction.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . .. . . . .1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . .. . . . 1
1.2 The Preliminaries in Graph Theory . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 2
2 Known Results . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . 6
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .. . . . 16



List of Figures

1.1 An IC-coloring of C4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
1.2 Two distinct maximal IC-colorings of C4. . . .. . . . . . . . . . . . . . . . . . . . . . . . 1
2.1 An IC-coloring of ST(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 An IC-coloring of K2,n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 An IC-coloring of ST(n,3^n). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 An IC-coloring of P5 and P6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.5 An IC-coloring s of C3 ,C4, C5, and C6. . . . . . . . . . . . . . . . . . . …. . . . . . . . .. . . . .4
3.1 An IC-coloring of k(1,m,n). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .. . . . . . . . . 7

Reference

[1] R. Alter, J. A. Brnett, A postage stamp problem, Amer. Math. Monthly 87(1980) 206-210.

[2] G. Chartrand, Introduction to graph theory, McGraw-Hill Higher Education, c2005.1st ed.

[3] C. C. Chen, On the IC-colorings of Split Graphs OmVK2, Department of Applied Mathematics Chung Yuan Christian University, July 2008.

[4] J. A. Gallian, A Dynamic survey of Graph Labeling, Electronic J. of combinatorial,3(2007).

[5] R. Guy, The Postage Stamp Problem, Unsolved Problems in Number Theory, second ed., Springer, New York, 1994, pp. 123-127.

[6] C. Y. Kuo, On the IC-colorings of complete tripartite graphs, Department of Applied Mathematics Chung Yuan Christian University, July 2011.

[7] S. Mossige, The postage problem: an algorithm to determine the h-range of the h-range
formula on the extremal basis problem for k = 4, Math. Comput. 69(2000) 325-337.

[8] S. G. Penrice, Some new graph labeling problems: a preliminary report, DI-MACS Tech. Rep. 95-26(1995) 1-9.

[9] E. Salehi, S. M. Lee, M. Khatirinejad , IC-colorings and IC-indices of graphs, Discrete Math. 299(2005) 297-310.

[10]C. L. Shiue and H. L. Fu, The IC-Indices of Complete Bipartite Graphs , The Electronic Journal of Combinatorics 15 (2008). #R43

[11]Y. C.Weng, On the IC-colorings of Split Graphs, Department of Applied Mathematics Chung Yuan Christian University, July 2008.