| 摘要: | 在2003年，圖論學者 G. Chartrand、T.W. Haynes、M.A. Henning 和 P. Zhang等四人提出分層支配問題，其定義如下：對於一個圖形Ｆ的每個點，我們著以藍色或紅色，若此圖形之點集合能按顏色分屬於兩個非空的子集合，則Ｆ被稱為二分層圖或Ｆ支配模板，而若一圖形Ｇ上每一個藍色點都能屬於一個複製的Ｆ支配模板的話，那麼Ｇ所含有的紅色點之個數，被稱為Ｇ的Ｆ支配數；所謂Ｆ支配數是指在給定圖形所形成的分層支配中，含紅色點數最小集合之點數大小。 自分層支配問題被提出迄今約五年的時間，已有超過二十篇以“分層支配＂為篇名之文獻以及至少兩篇博士論文。近兩年，學者R. Gera、M.A. Henning、P. Zhang 和 J.E. Ｍaritz 等人更大量提出有關分層支配問題之研究成果，譬如，分別以路徑P3、迴圈C3、迴圈C4等為指定模板，對於一般圖、樹狀圖以及一些特殊圖上之分別求解；另外，對於有向的規則網路，R. Gera 和 P. Zhang 等人以路徑3P 為指定模板，而提出規則網路的 3 P 支配數之上、下限值。由於本計劃所提出之研究乃是一個新興研究主題，儘管多位圖論領域的知名學者提出其研究結果，但是針對規則網路上求解分層支配數之相關文獻，據我們所知仍相當有限。 本計畫將試圖在分層支配問題剛開始為國際學者注視時，提出一系列研究。我們的研究團隊預計先針對一些規則網路，包括超立方圖、網格圖、星圖以及交換群圖，進行深入探討。在計畫的上半年，我們將先行審視評估規則網路本身的一些特性，預期在其中發現一些有關求解二分層支配問題的數學性質。植基於計畫上半年的研究結果，我們將於計畫的下半年再擴大研究成果，期望將建立對於先前擇訂之規則網路上有關分層支配研究之重要觀點(目前文獻尚未呈現者)，以提供一些關鍵性質，這將有助於發展更精確的研究。實際上，我們期望能夠對於本計畫所關切之規則網路的分層支配參數，運用固定參數演算法和一些圖形參數，例如獨立數、支配數以及全部支配數來定位其上下限值並求得有效率之演算法。
In 2003, G. Chartrand, T.W. Haynes, M.A. Henning and P. Zhang introduced several types of stratified domination in graphs, defined as follows. A graph G is 2-stratified if its vertex set is partitioned into two nonempty classes (each of which is a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red–blue coloring of the vertices of G such that for every blue vertex v of G, there is a copy of F in G rooted at v. Several bounds on different types of stratified domination numbers were obtained of a graph. Lately, R. Gera, M.A. Henning, P. Zhang and J.E. Ｍaritz boost up the research related to F-domination numbers of graphs, e.g. P3-domination number, C3-domination number, C4-domination number on general graphs, trees, and other special graphs. For directed regular graphs, R. Gera and P. Zhang gave lower bounds and upper bounds regarding 3P -domination. The investigation into the stratified domination problem was carried out by researchers while the results for solving the stratified domination numbers on regular graphs, to the best of our known, are poor. This project will seek to promote the line of research in the theory of stratified domination problem in the early beginning. Several regular graphs will be discussed. Regular graphs consist of hypercube, grids, star graphs, alternating group graphs, etc. During the first half year of this project, we shall survey the characteristics of the regular graphs for the purpose of exploring the mathematical properties of the stratified domination in such graphs. Based on the results obtained during the first half year of the study, our research of the second half year want to establish relevant aspects of the stratified domination of regular graphs, (not currently available in the literature), to provide essential properties which is needed for the development of a concise investigation. Actually, we would like to determine bounds on stratified domination numbers for the regular graphs in terms of other graph parameters, e.g. independence number, domination number and total domination number. Besides, we plan to explore efficient algorithms by using fixed-parameter techniques that was discussed in “2008 Talks and A Tutorial on Fixed-Parameter and Exact Algorithms”. |
