Signed Domination in Block Graphs

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：36

、訪客IP：3.139.72.126

姓名

龔欣如(Hsin-Ju Gong) 查詢紙本館藏

畢業系所

數學系

論文名稱

Signed Domination in Block Graphs
(Signed Domination in Block Graphs)

相關論文

★ Wide diameters and Rabin numbers of generalized folded hypercube networks	★ Distance-two domination of graphs
★ Strong Rabin Numbers on Cartesian Products of Graphs	★ Global defensive alliances in double-loop networks
★ 雙環網路距離二以內的控制問題	★ 廣義彼得森圖形的控制數

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(英)

In this thesis, we study the signed domination problem from an algorithmic point of view. In particular, we present some linear algorithms for finding the signed domination numbers of some special block graphs, such as block path and good block graph that every block of G has at least one vertex which is not a cut-vertex of G.

關鍵字(中)

★ Signed Domination
★ block graph

關鍵字(英)

★ signed domination
★ block graph

論文目次

Abstract........................................................ii
Contents.......................................................iii
1.Introduction....................................................1
2.Definitions and Notation........................................3
2.1Graphterminology.............................................3
2.2Domination,signed domination and related variation...........4
2.3Block graphs.................................................7
3.Signed Domination in Block Paths................................8
4.Signed Domination in Good Block Graph..........................15
References......................................................21

參考文獻

[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974.
[2] I. Broere, J.E. Dunbar and J.H. Hattingh, Minus k-subdomination in graphs. Ars Combin. 50 (1998) 177-186.
[3] I. Broere, J.H. Hattingh, M.A. Henning, and A.A. McRae, Majority domination in graphs, Discrete Math. 138 (1995) 125-135.
[4]K.S. Booth and J.H. Johnson, Dominating set in chordal graphs, SIAM I. Comput. 11(1982) 191-199.
[5] Gerard J. Chang and George L. Nemhauser, R-domination on block graphs, Operation Research Letters, vol. 1, no. 6, (1982) 214-218.
[6] Gerard J. Chang, Total domination in block graphs, Operation Research Letters 8 (1989) 53-57.
[7] Gerard J. Chang, Sheng-Chyang Liaw and Hong-Gwa Yeh, k-subdomination in graphs, Discrete Applied Math. 120 (2002) 55-60.
[8] E.J. Cockayne and C.M. Mynhardt, On a generalization of signed dominating functions of graphs, Ars Combin. 43 (1996) 235-245.
[9] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning, and P.J. Slater, Signed domination in graphs, Proceedings of the Seventh International Conference on Graph Theory, Combinatorics, Algorithms and Applications, 1994, pp. 311-321.
[10] O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287-293.
[11] M. Fischermann, Block graphs with unique minimum dominating sets, Discrete Math. 240 (2001) 247-251.
[12] M.R. Garey and D.S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-completeness, Freeman, New York(1979).
[13] F. Harary, A Characterization of block graphs, Canad. Math. Bull. Vol. 6 no. 1, Jan. 1963.
[14] J.H. Hattingh, M.A. Henning and P.J. Slater, On the algorithmic complexity of signed domination in graphs, Australas. J. Combin. 12 (1995) 101-112.
[15] J.H. Hattingh, E. Ungerer and M.A. Henning, Partial signed domination in graphs, Ars Combin. 48 (1998) 33-42.
[16] M.A. Henning, Domination in regular graphs, Ars Combin. 43 (1996) 263-271.
[17] M.A. Henning and P.J. Slater, Inequalities relating domination parameters in cubic graphs, Discrete Math. 158 (1996) 87-98.
[18] Le Tu Quoc Hung, Maciej M. Syslo, M.L. Weaver and D.B. West, Bandwidth and density for block graphs, Discrete Math. 189 (1998) 163-176.
[19] Li-Ying Kang, Chuangyin Dang, Mao-cheng Cai and Erfang Shan, Upper bounds for the k-subdomination number of graphs, Discrete Math. 247 (2002) 229-234.
[20] U.Tesohner, On the bondage number of block graphs, Ars Combin. 46 (1997) 25-32.
[21] Hong-Gwa Yeh and Gerard J. Chang, Algorithmic aspects of majority domination, Taiwanese J. Math. Vol. 1, no. 3, 343-350, Sep. 1997.
[22] B. Zelinka, Some remarks on domination in cubic graphs, Discrete Math. 158 (1996) 249-255.

指導教授

廖勝強(Sheng-Chyang Liaw)

審核日期

2004-7-6

推文