臺灣博碩士論文加值系統

　　令$G$為一個圖，且$f$為一個函數，使得$G$中的每一個頂點都對應至一個正整數。同時定義$f(H)=Sigma_{v in V(H)}f(v)$，
其中$H$為$G$的子圖。如果對於每一個正整數 $k in [1,f(G)]$，皆存在$G$的一個連通子圖$H$，使得$f(H)=k$，則我們稱$f$為
$G$的一個IC-著色。很顯然的，對於任意的連通圖$G$至少存在一個IC著色。圖$G$的IC-指數定義為$M(G)= maxleftlbrace f(G)mid
ight.$ $f$為圖$G$的一個IC著色$
brace$。如果$f$是$G$的一個IC著色，使得$f(G)=M(G)$，則我們稱$f$為$G$的一個極大IC著色。
在這一篇論文中，我們證明 $M(K_{m_{1},m_{2},m_{3}})= 13cdot2^{m_{1}+m_{2}+m_{3}-4}-3cdot2^{m_{1}-2}+4$ 當 $2leq m_{1}leq m_{2}leq m_{3}$。

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)=Sigma_{v in V(H)}f(v)$ for each subgraph $H$ of $G$. We say $f$ to be an extit{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 extit{IC-index} of a graph $G$, denoted by $M(G)$, is defined to be $M(G)= maxleftlbrace f(G)mid
ight.$ $f$ is an IC-coloring of $left. G
ight
brace$. 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 prove that $M(K_{m_{1},m_{2},m_{3}})= 13cdot2^{m_{1}+m_{2}+m_{3}-4}-3cdot2^{m_{1}-2}+4$ for $2leq m_{1}leq m_{2}leq m_{3}$.

目錄
授權書. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I
論文口試委員審定書. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II
中文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV
謝誌. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V
目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VI
圖目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VII
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The Preliminaries in Graph Theory . . . . . . . . . . . . . . . . . . . 2
2 Known Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
參考文獻. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
圖目錄
1.1 An IC-coloring of C4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Two distinct maximal IC-colorings of C4 . . . . . . . . . . . . . . . . 2
2.1 An IC-coloring of ST(n) . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 An IC-coloring of K2;n . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 An IC-coloring of ST(n; 3n) . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 An IC-coloring of P5 and P6 . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 An IC-coloring of C3;C4;C5;C6 . . . . . . . . . . . . . . . . . . . . . 5
3.1 An IC-coloring of K3;3;3 . . . . . . . . . . . . . . . . . . . . . . . . . . 8

{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 $1^{st}$ ed..
{3} Chien-Chang Chen， On the IC-colorings of Split Graphs $O_{m} vee K_{2}$, 中原應用數學系論文, 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} 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.
{7} S. G. Penrice, Some new graph labeling problems: a preliminary report, DIMACS Tech. Rep. 95-26(1995) 1-9.
{8} E. Salehi, Sin-Min Lee, M. Khatirinejad, IC-colorings and IC-indices of graphs, Discrete Math. 299(2005) 297-310.
{9} Chin-Lin Shiue and Hung-Lin Fu, The IC-Indices of Complete Bipartite Graphs, The Electronic Journal of Combinatorics 15 (2008). #R43
{10} Yun-Chun Weng，On the IC-colorings of Split Graphs, 中原應用數學系論文, 2008.
{11} B. G. Xu， “關於連通圖的IC-著色”， 華東交通大學學報， Vol.23 No.1 Feb., 2006.