English  |  正體中文  |  简体中文  |  Items with full text/Total items : 52572/87736 (60%)
Visitors : 9378640      Online Users : 104
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/102162

    Title: 羅馬控制數的探討
    Other Titles: The study of Roman domination number
    Authors: 許智雄;Xu, Zhi-Xiong
    Contributors: 淡江大學數學學系碩士班
    高金美;Kau, Chin-Mei
    Keywords: 蜘蛛圖;一般蜘蛛圖;羅馬控制數;spider graph;generalized spider graph;Roman domination number
    Date: 2014
    Issue Date: 2015-05-04 09:48:56 (UTC+8)
    Abstract: 在一個圖G=(V,E)上, 定義一個函數 f 將V對應到{0, 1, 2},假如f滿足每一個對應到0 的點都有一個對應到2的鄰居,函數 f 稱為羅馬控制函數。函數f的權重為圖中所有點相應的權重總和,而所有可能的羅馬控制函數中權重最小者稱為圖 G 的羅馬控制數。一個蜘蛛圖
    G(k_1,k_2,k_3,…,k_t )為含有共同端點的t個路徑〖 P〗_(k_1 ), 〖 P〗_(k_2 ), …, 〖 P〗_(k_t )所形成的圖。一個一般蜘蛛圖〖 C〗_t (k_1,k_2,k_3,…,k_t )是由一個迴圈〖 C〗_t=(1,2,3,…,t) 及t個點相異的路徑的聯集,此t個路徑分別與〖 C〗_(t )交於相異的一點且與〖 C〗_(t )交於點i的路徑為〖 P〗_(k_i )。在此論文中,我們分別獲得蜘蛛圖G(k_1,k_2,k_3,…,k_t )之控制數與羅馬控制數的計算方法,進而利用蜘蛛圖之羅馬控制數得到 γ_R (C_3 (k_(1 ), k_2, k_3 )) 以及
    γ_R (C_4 (k_1,k_2,k_3,k_4 ))的計算方法,同時獲得〖 γ〗_R (C_5 (n_1,n_2,n_3,n_4,n_5 ))及γ_R (C_6 (n_1,n_2,n_3,n_4,n_5,n_6 ))=γ_R (C_3 (n_1,n_2,n_3 ))+γ_R (C_3 (n_4,n_5,n_6 ))之猜想。
    Given a graph G = (V, E). We define a function f from V to {0, 1, 2}. The function f is called a Roman dominating function on G when satisfying the condition that every vertex v_i with f(v_i)=0 must be adjacent to at least one vertex v_j with f(v_j)=2. The weight of Roman dominating function f is the sum of the weight of each vertex of G. The minimum weight of all possible Roman dominating functions on G is the Roman domination number of G, denoted by γ_R (G). A spider graph G(k_1,k_2,k_3,…,k_t ) is the union of t paths〖 P〗_(k_1 ), 〖 P〗_(k_2 ), …, 〖 P〗_(k_t )with one common end vertex. A generalized spider graph〖 C〗_t (k_1,k_2,k_3,…,k_t ) is the union of a t-cycle〖 C〗_t=(1,2,3,…,t) and t paths〖 P〗_(k_1 ), 〖 P〗_(k_2 ), …, 〖 P〗_(k_t ) where each path intersect Ct with exact one vertex and〖 P〗_(k_i ) intersect Ct at the vertex i.
    In this thesis, we obtain the formula to calculate the minimum domination number and Roman domination number of each spider graph. For the Roman domination number of a generalized spider graph, we obtain the formula of
    γ_R (C_3 (k_(1 ), k_2, k_3 )) and γ_R (C_4 (k_1,k_2,k_3,k_4 )) related to the Roman domination number of a spider graph. After that we give two conjectures about calculating γ_R (C_5 (n_1,n_2,n_3,n_4,n_5 )) and γ_R (C_6 (n_1,n_2,n_3,n_4,n_5,n_6 )).
    Appears in Collections:[數學學系暨研究所] 學位論文

    Files in This Item:

    File SizeFormat

    All items in 機構典藏 are protected by copyright, with all rights reserved.

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback