郵票問題的研究

Abstract

所謂的郵票問題是出版一套每一張面額皆不同的郵票，使得面額總和以內的每一個數都可以用彼此相連不分散的郵票湊出來。舉例來說，假如我們要發行一套最多三張郵票，面額分別是一元、二元和四元，則我們可以湊出一到七元的郵票，而且每一種組合的郵票彼此都是相連不分散的。 由上述的概念，我們可以把郵票問題的想法延伸到graph labeling上，用以下的方式：找一個圖G的labeling 函數 使得對於1到值和內的每一個值k，必定存在一個值和為k的連通子圖H。這樣的labeling方式就稱為圖G的IC-著色，圖G的所有IC-著色中最大的值和就是圖G的IC-指標。 在此篇論文當中，我們主要研究某些圖的IC-著色和改善圖的指標的上界和下界。還有，我們也考慮當 的情形，並研究是否圖G具有IC-著色；如果有的話，圖G就稱為可和飽和的。