支配問題是一個經典問題,可以應用於許多不同的實際問題上，給定一個圖形 G=(V,E)，一個點集合 D⊆V 是圖形 G 的支配集，表示任一個不在 D 中的點都有一個鄰居在 D 中。跳躍支配是支配問題的一種變體，目前尚未得到廣泛的研究。給定一個圖形 G=(V,E)，若一個點集合 S⊆V 滿足對 V 上的每一個不屬於 S 的點，都有一個以上在 S 的點與其距離為2，這個點集合 S 被稱為是圖形 G 的一個跳躍支配集。圖形 G 的最小跳躍支配集的元素個數以 〖 γ〗_h (G) 表示。網格圖(Grid graphs)又被稱為網狀圖(Mesh)，通常可以畫成二維的長方形格子圖，一般用 G_(m×n) 來表示，其中 m 表列數，n 為行數。在本研究中，我們計算任一個網格圖 G_(m×n) 的 〖 γ〗_h (G_(m×n)) 數值，針對 1≤m≤5 時，我們得出 〖 γ〗_h (G_(m×n)) 的最佳解，而 6≤m 時，我們計算 〖 γ〗_h (G_(m×n)) 的近似解。

Domination problem is a classical problem that can be applied on many different real applications. Given a graph G=(V,E), a vertex subset D⊆V is a dominating set if for every vertex v, v has a neighbor in D. Hop domination is a variant of domination problem which is not well-studied for the time being. For a graph G=(V,E), we say a vertex subset S⊆V is a hop dominating set of graph G if every vertex v∈V∖S there is a vertex u∈S such that the distance of u and v is 2. The minimum cardinality of a hop dominating set of 𝐺 is called the hop domination number of G and is denoted by〖 γ〗_h (G). Grid graphs are a kind of graphs that can be depicted as a two dimensional matrix. Usually, it is denoted as G_(m×n), where m is the number of rows and n is the number of columns. In this study, we compute 〖 γ〗_h (G_(m×n)). In particular, if 1≤m≤5, we find the optimal solutions for 〖 γ〗_h (G_(m×n)). However, for 6≤m, we obtain approximate solutions for 〖 γ〗_h (G_(m×n) ).

Chapter 1 Introduction 1
Chapter 2 Main Results 5
Chapter 3 Conclusion and Future Work 23
Bibliography 25

[1] B.D. Acharya & M.K. Gill, On the index of gracefulness of a graph and the gracefulness of two-dimensional square lattice graphs. Indian Journal Math Vol.23, 81-94, 1981.
[2] S.K. Ayyaswamy, B. Krishnakumari, C. Natarajan & Y.B. Venkatakrishnan, Bounds on the hop domination number of a tree, Proceedings - Mathematical Sciences Vol.125, 449–455, 2015.
[3] W. W. Rouse Ball, Mathematical Recreation and Problems of Past and Present Times, 1892.
[4] A. M. Barcalkin & L. F. German, The external stability number of the Cartesian product of graphs. Bul. Akad. ˘Stiince RSS Moldoven. no.1 5-8, 1979.
[5] S.C. Barman, M. Pal & S. Mondal, An optimal algorithm to find minimum k-hop dominating set of interval graphs, Discrete Mathematics Algorithms and Applications Vol.11(2), 1950016: 1–18, 2019.
[6] C. Berge, Theory of Graphs and its Applications. Methuen, London, 1962.
[7] G. Chen, W. Piotrowski & W. Shreve, A partition approach to Vizing’s conjecture. J. Graph Theory 21 103-111, 1996.
[8] E. J. Cockayne & S. T. Hedetniemi, Towards a theory of domination in graphs. Networks, 7:247-261, 1977.
[9] R.S. Coelho, P.F.S. Moura & Y. Wakabayashi, The k-hop connected dominating set problem: hardness and polyhedra, Electronic Notes in Discrete Mathematics Vol.50, 59–64, 2015.
[10] R.S. Coelho, P.F.S. Moura & Y. Wakabayashi, The k-hop connected dominating set problem: approximation and hardness, Journal of Combinatorial Optimization Vol.34, 1060–1083, 2017.
[11] R. J. Faudree, R. H. Schelp & W. e. Shreve, The domination number for the product of graphs. Congr. Numer. 79 29-33, 1990.
[12] C.X. gang & W.Y. feng, On total domination and hop domination in diamond-free graphs, Bulletin of the Malaysian Mathematical Sciences Society Vol.43, 1885–1891, 2020.
[13] B. L. Hartnell & D. F. Rall, Vizings conjecture and the one-half argument. Discuss. Math. Graph Theory, 15(2):205-216, 1995.
[14] M.A. Henning & N.J. Rad, On 2-step and hop dominating sets in graphs, Graphs and Combinatorics Vol.33:913–927, 2017.
[15] M.A. Henninga, S. Palb & D. Pradhanb, Algorithm and hardness results on hop domination in graphs, Information Processing Letters Vol.153, 105872: 1–8, 2020.
[16] C. F. De Jaenisch, Applications de l’Analyse mathematique an Jen des Echecs, 1862.
[17] D.A. Mojdeh & A.S. Emadi, Hop domination polynomial of graphs, Journal of Discrete Mathematical Sciences and Cryptography, 1–16, 2019.
[18] C. Natarajan & S.K. Ayyaswamy, Hop domination in graphs-II, Versita Vol. 23(2),187–199, 2015.
[19] O. Ore, Theory of Graphs. Amer. Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence, RI), 1962.
[20] N.J. Rad, A. Poureidi, On hop roman domination in trees, Communications in Combinatorics and Optimization Vol.4(2), 201–208, 2019.
[21] R.C. Rakim, C.J.C. Saromines & H.M. Rara, Perfect hop domination in graphs, Applied Mathematical Sciences, Vol.12(13), 635–649, 2018.
[22] Jennifer M. Tarr, Domination in Graphs, Graduate Theses and Dissertations, 2010.
[23] V. G. Vizing, The Cartesian product of graphs. Vy˘cisl. Sistemy 9: 30-43, 1963.
[24] H.D. Yang, A study of disjunctive total domination problem on tori and grid graphs, National Dong Hwa University Thesis.
[25] Y. Zhao, L. Mia & Z. Liao, A linear-time algorithm for 2-step domination in block graphs, Journal of Mathematical Research with Applications Vol.35(3), 285–290, 2015.