臺灣博碩士論文加值系統

令 G 為一個圖，圖上每一個點的度至少為二。 G 上的點集合稱二元組完全支配集，在 G 上的任何一個點至少有兩個鄰居在集合 S 內。二元組完全支配數是最小二元組完全支配集的大小。在本篇論文我們探討 Harary 圖 H_{2m+1,2n+1} 點數為 2n+1=(2m+1)\ell 的二元組完全支配數，當 m = 1 和 m = 2 我們給了二元組完全支配數為 2\ell 和 2\ell+1。

Let G be a graph with minimum degree at least 2. A vertex subset is a 2-tuple total dominating set of G if every vertex is adjacent to at least two vertices in S. The 2-tuple total domination number of G is the minimum size of a 2-tuple total dominating set. In this thesis, we are concerned with the 2-tuple total domination number of a Harary graph H_{2m+1, 2n+1} with 2n+1=(2m+1)\ell. For m = 1 and m = 2, we show that the numbers are 2\ell and 2\ell+1, respectively.

摘要I
Abstract II
誌謝III
目錄IV
表目錄VI
圖目錄VII
1 緒論2
1.1 背景. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Harary 圖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 二元組完全支配問題. . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 相關研究. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 性質12
3 主要研究15
3.1 二元組完全支配數在H3;2n+1 . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 二元組完全支配數在H5;2n+1 . . . . . . . . . . . . . . . . . . . . . . . 20
4 未來研究及討論38
參考文獻39

[1] E. J. Cockayne, R. Dawes, S. T. Hedetniemi, ``Total domination in graphs,'' $Networks$, vol. 10, pp. 211--215, 1980.

[2] J. Gimbel, M. Mahéo, C. Virlouvet, ``Double total domination of graphs,'' $Discrete$ $Mathematics$, vol. 165--166, pp. 343--351, 1997.

[3] F. Harary, ``The maximum connectivity of a graph,'' $Proceedings$ $of$ $the$ $National$ $Academy$ $of$ $Sciences$ $of$ $the$ $United$ $States$ $of$ $America$, vol. 48, pp. 1142--1146, 1962.

[4] M. A. Henning, ``A survey of selected recent results on total domination in graphs,'' $Discrete$ $Mathematics$, vol. 309, pp. 32--63, 2009.

[5] M. A. Henning, A. P. Kazemi, ``$k$-tuple total domination in graphs,'' $Discrete$ $Applied$ $Mathematics$, vol. 158, pp. 1006--1011, 2010.

[6] 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.

[7] M. Hussain, E.T. Baskoro, K. Ali, ``On super antimagic total labeling of Harary graph'', $Ars$ $Combinatoria$, vol.104, pp. 225--233, 2012.

[8] A. P. Kazemi, B. Pahlavsay, ``Double total domination in Harary graphs,'' arXiv:1603.02430.

[9] A. P. Kazemi, P. Jalilolghadr, ``Chromatic number of Harary graphs,'' $Tbilisi$ $Mathematical$ $Journal$, vol. 9, no. 1, pp. 271--278, 2016.

[10] J.M. Keil, ``The complexity of domination problems in circle graphs,'' $Discrete$ $Applied$ $Mathematics$, vol. 42, pp.51--63, 1993.

[11] A. Khodkar, D. A. Mojdeh, A. P. Kazemi, ``Domination in Harary graphs'', $Bull.$ $ICA$, vol. 49, pp. 61--78, 2007.

[12] J. K. Lan, G. J. Chang, ``On the algorithmic complexity of $k$-tuple total domination,'' $Discrete$ $Applied$ $Mathematics$, vol. 174, pp. 81--91, 2014.

[13] R.C. Laskar, J. Pfaff, S.M. Hedetniemi, S.T. Hedetniemi, ``On the algorithmic complexity of total domination,'' $SIAM$ $Journal$ $Algebraic$ $Discrete$
$Methods$, vol. 5, no. 3, pp. 420--425, 1984.

[14] C. S. Liao, G. J. Chang, ``Algorithmic aspect of $k$-tuple domination in graphs,'' $Taiwanese$ $Journal$ $of$ $Mathematics$, vol. 6, no. 3, pp. 415--420, 2002.

[15] A.A. McRae, ``Generalizing NP-completeness proofs for bipartite and chordal graphs,'' Ph.D. Thesis, Clemson University, 1994.

[16] D. A. Mojdeh, A. P. Kazemi, ``Defining numbers in some of the Harary graphs,'' $Applied$ $Mathematics$ $Letters$, vol. 22, no.6, pp. 922--926, 2009.

[17] J. Pfaff, R.C. Laskar, S.T. Hedetniemi, ``NP-completeness of total and connected domination and irredundance for bipartite graphs,'' $Technical$
$Report$ 428, Clemson University, Dept. Math. Sciences, 1983.

[18] D. Pradhan, ``Algorithmic aspects of $k$-tuple total domination in graphs,'' $Information$ $Processing$ $Letters$, vol. 112, pp. 816--822, 2012.

[19] T. Ramachandran, A. N. Ahmed, ``Dominating-$\chi$-color number of Harary graph,'' $International$ $Journal$ $of$ $Science$ $and$ $Research$, vol. 4, no. 3, 2015.

[20] D. B. West, $Introduction$ $to$ $Graph$ $Theory$, 2nd ed., Prentice Hall USA, 2001.