整數之控制數研究

Abstract

假設 G 為一個圖，V 為圖 G 的點集合，E 為圖G的邊集合。對任意正整數 k，若有一函數 f 從 G 的點集合 V 對應到非負整數，使得對於 G 中的任意點 v 之函數值及與點 v 相連的所有點之函數值總和大或等於 k，則我們稱此對應函數 f 為 G 的一個{k}-控制函數。函數 f 的權重是 G 的點集合之函數值之總和。若 f 是 G 的一個{k}-控制函數，則最小的權重值稱之為{k}-控制數，記做γ_{k}(G)。我們可以清楚地知道當 k = 1 時，{k}-控制數的問題恰好是控制數的問題。這個結論也說明了{k}-控制數的研究推廣了圖論中最重要的問題之一：控制數的研究。在這篇論文中，對任意圖的γ_{k}(G) 我們得到好的估計值。而且我們著重在研究格子圖P_m □P_n 上，我們決定了γ_{k}(P_2□P_n)，也得到了γ_{k}(P_m□P_n) 的上下界。

Let G = (V,E) be a graph. For integer k ≥ 1, a function f : V →N∪{0} is a {k}-dominating function if for every v∈V,f(v)+Σ_uv∈E f(u)≥k. The weight of f is Σ_v∈V f(v). The {k}-domination number, denoted by γ_{k}(G), of G is the minimum weight of a {k}-dominating function. Clearly, when k = 1, a {k}-domination problem is exactly the domination problem. Therefore, this study is a generalization of the domination problem on graphs. In this thesis, we obtain a good estimation of γ_{k}(G) for all graphs. And we focus on grid graphs P_m□P_n. As a consequence, we determine the exact value of γ_{k}(P_2□P_n), and give bounds on γ_{k}(Pm□Pn).