臺灣博碩士論文加值系統

令 G = (V, E) 為一個最小分支度至少是 2 的圖。若在圖 G 中的點集合 D 滿 足圖上的每一個點都有至少 2 個相鄰點落在 D 中,則 D 稱為二多重完全支配 集。圖 G 上的二多重完全支配數表示為 γ×2,t(G) ,是最小二多重完全支配集的元 素個數。
本論文探討 Harary 圖 H_(2m+1,2n) (其中 2m + 1 為分支度,2n 為點數) 的二 多重完全支配問題。令 2n = (2m + 1)l + r , 0<= r<= 2m,當 r = 0 或 m + 1 <= r<= 2m 時, γ×2,t(H2m+1,2n) 已知 [Kazemi,Pahlavsay,Double total domination in Harry graphs,Communications in mathematics and applications]; 本論文針對 1 <=r <= m 且 m = 1 或 2 的情形做探討。研究結果顯示當 m = 1 時, 若 n−2 是 6 的倍數,則 γ×2,t(H2m+1,2n) = 2l+1 , 否則 γ×2,t(H_(2m+1,2n)) = 2l+2; 當 m = 2 時, γ×2,t(H_(2m+1,2n)) = 2l + 2 。

Let G = (V, E) be a graph with minimum degree at least 2. A vertex subset D is a double total dominating set of G if every vertex of G is adjacent to at least two vertices in D. The double total domination number of G, denoted as γ×2,t(G), is the size of a minimum double total dominating set in G.
In this thesis, we are concerned with the double total domination number of the Harary graph H_(2m+1,2n), where 2m + 1 is the degree of each vertex and 2n is the number of vertices. Let 2n = (2m+1)l+r, where 0 <= r <= 2m. When r = 0 or m + 1 <= r <= 2m, γ×2,t(H_(2m+1,2n)) is known [Kazemi and Pahlavsay, Double total domination in Harry graphs, Communications in Mathematics and Applications]. In this thesis, we are concerned with the case where 1 <= r <= m and m ∈ {1,2}. We obtain the following results: (i) For m = 1, γ×2,t(H_(2m+1,2n)) = 2l+1 if n−2 is divisible by 6, and γ×2,t(HH_(2m+1,2n)) = 2l+2 otherwise. (ii) For m = 2, γ×2,t(H_(2m+1,2n)) = 2l+2.

Contents
摘 要-------------- I
Abstract ----------II
誌 謝------------- III
Contents---------- IV
List of Tables-------- V
List of Figures ----------VII
1 Introduction ------------1
2 Preliminaries--------- 8
3 Main Results -----------11
3.1 DoubletotaldominationinH3,2n .................... 11 3..2DoubletotaldominationinH5,2n .................... 16
4 Conclusions----------------39
References-----------------------40

References
[1] B. Chaluvaraju, V. Chaitra, Total domination polynomial of a graph, Journal of Informatics and Mathematical Sciences, vol. 6, pp. 87–92, 2014.
[2] E.J. Cockayne, R. Dawes, S.T. Hedetniemi, Total domination in graphs, Net- works, vol. 10, pp. 211–215, 1980.
[3] F. Harary, The maximum connectivity of a graph, Proceedings of the National Academy of Sciences, vol. 48, pp. 1142–1146, 1962.
[4] M.A. Henning, A.P. Kazemi, k-tuple total domination in graphs, Discrete Ap- plied Mathematics, vol. 158, pp. 1006–1011, 2010.
[5] M.A. Henning, A.P. Kazemi, k-tuple total domination in cross product of graphs, Journal of Combinatorial Optimization, vol. 24, pp. 339–346, 2012.
[6] M. Hussain, E.T.P. Baskoro, K. Ali, On super antimagic total labeling of Harary graph, Ars Combinatoria, vol. 104, pp. 225–233, 2012.
[7] A.P. Kazemi, k-tuple total domination in complementary prisms, ISRN Discrete Mathematics, vol. 2011, Article ID 681274, 2011.
[8] A.P. Kazemi, A note on the k-tuple total domination number of a graph, Tbilisi Mathematical Journal, vol. 8, no. 2, pp. 281–286, 2015.
[9] A.P. Kazemi, P. Jalilolghadr, Chromatic number of Harary graphs, Tbilisi Mathematical Journal, vol. 9, no. 1, pp. 271–278, 2016.
[10] A.P. Kazemi, B. Pahlavsay, Double total domination in Harary graphs, Com- munications in Mathematics and Applications, vol. 8, no. 1, pp. 1–6, 2017.
[11] J.M. Keil, The complexity of domination problems in circle graphs, Discrete Applied Mathematics, vol. 42, pp. 51–63, 1993.
[12] A. Khodkar, D.A. Mojdeh, A.P. Kazemi, Domination in Harary graphs, Bull. ICA, vol. 49, pp. 61–78, 2007.
[13] R.C. Laskar, J. Pfaff, S.M. Hedetniemi, S.T. Hedetniemi, On the algorithmic complexity of total domination, SIAM Journal on Algebraic Dscrete Methods, vol. 5, no. 3, pp. 420–425, 1984 .
[14] J.K. Lan, G.J. Chang, On the algorithmic complexity of k-tuple total domina- tion, Discrete Applied Mathematics, vol. 174, pp. 81–91, 2014.
[15] A.A. McRae, Generalizing NP-completeness proofs for bipartite and chordal graph, Ph.D. Thesis, Clemson University, 1994.
[16] J. Pfaff, R.C. Laskar, S.T. Hedetniemi, NP-completeness of total and connected domination and irredundance for bipartitle graphs, Technical Report 428, Clem- son University, Dept. Math. Sciences, 1983.
[17] D. Pradhan, Algorithmic aspects of k-tuple total domination in graphs, Infor- mation Processing Letters, vol. 112, pp. 816–822, 2012.
[18] T. Ramachandran, A.N. Ahmed, Dominating-x-color number of Harary graph, International Journal of Science and Research, vol. 4, no. 3, pp. 672–674, 2015.
[19] D.B. West, Introduction to Graph Theory, 2nd edition, Prentice Hall, USA (2001).
[20] S.-H. Yang, H.-L. Wang, A note on the 2-tuple total domination problem in Harary graphs, Proceedings of International Computer Symposium (ICS 2016), Dec. 15–17, Chiayi, Taiwan.