整數之控制數研究

A study of integer domination number

關玉婷(Yu-Ting Kuan)

指導教授 ： 傅恆霖

國立交通大學/理學院/應用數學系暨研究所/碩士(2017年)

摘要

假設 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).

並列關鍵字

domination ； integer

參考文獻

[1] B. Brešar , M.A. Henning, S. Klavžar, On integer domination in graphs and vizing-like problems, Taiwan J. Math. 10 (2006), 1317-1328.

[2] Gray Chartrand, Ping Zhang, Introduction to Graph theory, McGraw Hill, Higher Education (2005).

[3] G. Domke, S.T. Hedetniemi, R.C. Laskar, G. Fricke, Relationships between integer and fractional parameters of graphs, in: Graph Theory, Combinatorics, and Applications, vol.2, John Wiley & Sons, Inc. (1991), 371-287.

[4] D. Gonçalves, A. Pinlou, M. Rao, S. Thomassé, The domination number of grid graphs, SIAM J. Discrete Math. 2011, 25, pp.1443-1453.

[5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Deliker, New York (1998).