簡易檢索 / 詳目顯示

回結果列表
研究生： 柯孟豪
Meng-Hao Ko
論文名稱： 在通式化迪布恩有向圖中之彩虹支配問題
Rainbow Domination in Generalized de Bruijn Digraphs
指導教授： 王有禮
Yue-Li Wang
口試委員: 徐俊傑
Chiun-Chieh Hsu
劉嘉傑
Jia-Jie Liu
學位類別： 碩士
Master
系所名稱： 管理學院 - 資訊管理系
Department of Information Management
論文出版年： 2014
畢業學年度： 102
語文別： 英文
論文頁數： 24
中文關鍵詞： 支配 、彩虹支配問題 、通式化迪布恩有向圖
外文關鍵詞： Domination, Rainbow domination, Generalized de Bruijn digraph
相關次數： 點閱：279  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  •  上一筆

    • 在本篇論文中，我們考慮了在通式化迪布恩有向圖上面的k-彩虹支配問題。
    我們提出了一個k-彩虹支配數的下限為max{k;⌈kn/(d+k)⌉}， 而上限為k⌈n/d⌉。而且當\gamma rk(GB(n, d)) = k 時其充分且必要條件為 \alpha ≤ 1 其中n = d + \alpha 。另外，我們討論了在某些情形，可以得到更小的上限。

    In this thesis, we are concerned with the k-rainbow domination problem on generalized de Bruijn digraphs. We give an upper bound and a lower bound for the k-rainbow domination number in generalized de Bruijn digraphs GB(n; d). We show that \gamma rk(GB(n, d)) = k if and only if \alpha ≤ 1, where n = d + \alpha and rk(GB(n, d)) is the k-rainbow domination number of GB(n, d). We also discuss the class of generalized de Bruijn digraphs with \gamma rk(GB(n, d)) ≤ k⌈ n/(d+1)⌉.

    1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Related Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Preliminaries 10 2.1 Graph Terminology and Notation . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 De nition of generalized de Bruijn digraphs . . . . . . . . . . . . . . . . . . 10 2.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 The k-Rainbow Domination Numbers of Generalized de Bruijn Digraphs 13 3.1 The class of generalized de Bruijn digraphs with \gamma rk(GB(n, d)) = k . . . . . 14 3.2 The class of generalized de Bruijn digraphs with \gamma rk(GB(n, d)) ≤ k⌈ n/(d+1)⌉ . . 19 4 Conclusion Remarks 22

    [1] T. Araki, On the k-tuple domination in de Bruijn and Kautz digraphs, Information Processing Letters 104 (2007) 86-90.
    [2] T. Araki, The k-tuple twin domination in de Bruijn and Kautz digraphs, Discrete Mathematics 308 (2008) 6406-6413.
    [3] J.-C. Bermond, C. Peyrat, de Bruijn and Kautz networks: a competitor for the
    hypercube?, in:, F. Andr e , J.P. Verjus (Eds.), Hypercube and Distributed Computers, Elsevier Science Publishers B.V. (North-Holland), Amsterdam 1989, pp. 279-293.
    [4] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Elsevier, North Holland, New York 1986.
    [5] B. Bre^sar, T.K. ^Sumenjack , On the 2-rainbow domination in graphs, Discrete Apllied Mathematics 155 (2007) 2394-2400.
    [6] B. Bre^sar, M.A. Henning, D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213-225.
    [7] G.J. Chang, J. Wu, X. Zhu, Rainbow domination on trees, Discrete Apllied Mathematics 158 (2010) 8-12.
    [8] D.Z. Du, F.K. Hwang, Generalized de Bruijn digraphs, Networks 18 (1988) 27-38.
    [9] D.Z. Du, D.F. Hsu, F.K Hwang, X.M. Zhang, The hamiltonian property of generalized de Bruijn digraphs, Journal of Combinatorial Theory Series B 52 (1991) 1-8.
    [10] J.Ghoshal, R. Laskar, D. Pillone, Topics on domination in directed graphs, in: T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York 1998, pp. 401-437.
    [11] T. Hasunuma, Y. Shibata, Counting small cycles in generalized de Bruijn digraphs, Networks 29 (1997) 39-47.
    [12] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York 1998. 23
    [13] N. Homobono, C. Peyrat, Connectivity of Imase-Itoh digraphs, IEEE Transactions on Computers 37 (1988) 1459-1461.
    [14] M. Imase, M. Itoh, Design to minimize diameter on building-block networks, IEEE Tansactions on Computers 30 (1981) 439-442.
    [15] M. Imase, M. Itoh, A design for directed graphs with minimum diameters, IEEE Transactions on Computers 37 (1983) 782-784.
    [16] M. Imase, T. Soneoka, K. Okada, Connectivity of regular directed graphs with small diameters, IEEE Tansactions on Computers 34 (1985) 267-273.
    [17] Y. Kikuchi, Y. Shibata, On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs, Information Processing Letters 86 (2003) 79-85.
    [18] Jyhmin Kuo, On the twin domination numbers in generalized de Bruijn and geralized Kautz digraphs, Discrete Mathematics Algorithms and Applications 2 (2010) 199-205.
    [19] X. Li, F. Zhang, On the numbers of spanning trees and Eulerian tours in generalized de Bruijn graphs, Discrete Mathematics 94 (1991) 189-197.
    [20] E.F. Shan, T.C.E. Cheng, L.Y. Kang, Absorbant of generalized de Bruijn digraphs, Information Processing Letters 105 (2007) 6-11.
    [21] E.F. Shan, Y.X. Dong, Y.K. Cheng, The twin domination in generalized de Bruijn digraphs, Information Processing Letters 109 (2009) 856-860.
    [22] E.F. Shan, Y.X. Dong, The k-tuple twin domination in generalized de Bruijn and Kautz networks, Computers and Mathematics with Applications 63 (2012) 222-227.
    [23] Y. Shibata, M. Shirahata, S. Osawa, Counting closed walks in generalized de Bruijn graphs, Information Processing Letters 49 (1994) 135-138.
    [24] F. Tian, J.-M Xu, Distance domination numbers of generalized de Bruijn and Kautz digraphs, Or Transactions 10 (2006) 88-94.
    [25] L.Y. Wu, E.F. Shan, Z.R. Liu, On the k-tuple domination in generalized de Bruijn and Kautz digraphs, Information Scinece 180 (2010) 4430-4435.

    QR CODE