跳到主要內容

臺灣博碩士論文加值系統

(3.229.142.104) 您好!臺灣時間:2021/07/30 16:02
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:龔欣如
研究生(外文):Hsin-Ju Gong
論文名稱:SignedDominationinBlockGraphs
論文名稱(外文):Signed Domination in Block Graphs
指導教授:廖勝強
指導教授(外文):Sheng-Chyang Liaw
學位類別:碩士
校院名稱:國立中央大學
系所名稱:數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:25
中文關鍵詞:Signed Dominationblock graph
外文關鍵詞:signed dominationblock graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:139
  • 評分評分:
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
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.
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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top