探討卡氏積生成圖裡有關不可移動控制集及相關標號問題;The Study of Blocking Dominating Sets and Related Labeling Problems on Cartesian Product of Graphs

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/82392

Title:	探討卡氏積生成圖裡有關不可移動控制集及相關標號問題;The Study of Blocking Dominating Sets and Related Labeling Problems on Cartesian Product of Graphs
Authors:	廖勝強
Contributors:	國立中央大學數學系
Keywords:	不可移動控制集;卡氏積生成圖;blocking dominating set;Cartesian product of graphs
Date:	2020-01-13
Issue Date:	2020-01-13 14:50:05 (UTC+8)
Publisher:	科技部
Abstract:	在一個區域範圍內, 假設我們要設置一些可移動式的無線基地台來架構一個涵蓋整個區域無線網路服務, 而且在移動的過程中, 仍然要維持無線網路中的設備連線不中斷. 那麼需要多少基地台就保證可移動呢? 因此我們將此問題轉化成控制集的問題, 對給定的圖探討怎樣的建置使得這些基地台都無法移動, 並且找到這不可移動的建置裡所使用最多基地台的數目. 換言之, 若一開始的基地台建置數超過這個數目就可移動. ;A hotspot is a physical location where people may obtain Internet access, typically using Wi-Fi technology, via a wireless local area network (WLAN) using a router connected to an internet service provider. Due to a practical application, those hotspots could be movable, called mobile servers, in the distribution problem over an area. So Fujita propose the problem ``How to provide continuous services by mobile servers in communication networks? '' This problem could be considered as a variation of the domination problem with a new model of network services in which each server associated to a vertex can move to any adjacent vertex in a single step. In each step, at most one server can move to an adjacent vertex. For nonstop service, the set of vertices associated with the servers forms a dominating set on the given network all the time. For technical reason, this kind of dominating set may be a multiset. A safe move of a dominating set means that we move a server to a neighbor to form a new dominating set. In a given graph G, a dominating (multi)set with size k is transferable if and only if it can be transfer to any dominating (multi)set of G with the same size k through a sequence of safe moves. Recently, Chu proved that for the class of connected strongly chordal graph, any dominating set is transferable.Base on Fujita's problem, we will study the revised labeling function with respect to the vertex multiset D which is chosen from V(G) by assigning f_D (v) to be its multiplicity in D.We call the above labeling function a configuration of G with size \|D\|. A configuration is blocking if there does not exist a safe move for the configuration. Clearly, it is always blocking if the size of a configuration of G is less than its domination number. The related dominating multiset of a blocking configuration is called a blocking dominating set since there is always a safe move if D is a dominating multiset and f_D(v) is at least 2 for some v in D. The blocking domination number of G is the maximum size of a blocking configuration of G. During the past year, we have determined the blocking domination number of C_n and some Cartesian product of P_n and P_m. So we will extend our results to more cartesian product graphs in the next two years.
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Mathematics] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	253	View/Open

社群 sharing

Loading...