摘要
令$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}$.
參考文獻
延伸閱讀
- Tsai, C. H. (2012). 完全三分圖Ｋ（１，ｍ，ｎ）的IC著色 [master's thesis, Chung Yuan Christian University]. Airiti Library. https://doi.org/10.6840/cycu201200233
- 張敏南（2009）。完全三分圖K(1,m,n)的IC-著色研究〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu200900751
- Lung, C. L. (2012). 考慮可靠度之三維晶片設計 [doctoral dissertation, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2012.00494
- Chang, H. C. (2014). 使用線段一致性從單張影像估測三維室內曼哈頓場景 [master's thesis, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2014.00636
- Weng, Y. C. (2008). On the IC-Colorings of Split Graphs [master's thesis, Chung Yuan Christian University]. Airiti Library. https://doi.org/10.6840/CYCU.2008.00414