| Abstract: | 本計畫從事圖形的標號、著色、分割、與覆蓋之相關研究。我們將以有限幾何，??，群?等工具以及其他標準組合學方法研究以下幾?相關問題: ? 圖形的L(2, 1)-標號(距?二型態標號)為一非負整?的頂點標號，使得距?至多是2的頂點之標號相?，而且相鄰頂點標號差至少是2。本計畫方向之一是在探討未解問題Griggs-Yeh Conjecture。? 一個具有p個頂點及q個邊的有限無向單圖，其反幻方標號(antimagic labeling)為一邊標號，也就是從邊集合映到整? 1, 2, ...... , q 之對射，使得每一頂點之頂點和(vertex sum)皆?同，其中頂點和是與此頂點?接的所有邊標號的和。Nora Hartsfield 與 Gerhard Ringel 猜測: 除?K2外，所有?通圖皆具有反幻方標號。2004 ?，Noga Alon等人證明，對於邊?稠密的圖(dense graphs)，此猜測為真。本計畫將針對邊?稀少的反幻方圖?，進一步對Hartsfield-Ringel 猜測的解決提供想法。? ?(Zk, +, 0) 為關於 k > 1 同餘?所成加法循環群，對一個有限簡單無向圖G，其Zk -幻方標號(Zk -magic labeling)為一組邊標號 f: E(G) ? Zk - {0}，使得每一頂點之頂點和(vertex sum) mod k皆同。刻劃Zk-magic圖形仍然為困難之未解問題。我們記所有可能之magic sum constants為 magic sum spectrum, 本計畫將針對各?圖形之 magic sum spectrum 研究。? 著色問題的一?推廣是可選性(choosability)問題或稱?表著色(list coloring)問題。在著色問題中，各個元素從同樣的顏色集合被分配一種顏色。在可選性問題中，各個元素有任意自己的?表顏色集合，並且各個元素從自己的?表顏色集合被分配一種顏色?著色。本計畫將針對Steinberg猜想研究相關未解問題。? 圖的邊集合的團覆蓋(或團分割)問題就是：對於一給定圖形，尋找最少?目的團(clique)，使得每一個邊至少(或恰好)包含在某個團之中。Fred Roberts, Walter Wallis等人考慮那些需要所有的極大團形成邊集合的最小團覆蓋的圖?，並稱之為極大團?可約圖(maximal clique irreducible graphs)。我們考慮極大團?可約圖形的刻劃問題，並且推廣到一?大範圍之圖?，即弱極大團?可約圖(weakly maximal clique irreducible graphs)。我們關於弱極大團?可約圖，所得到的主要結果，是繼承性?允許子圖結構(forbidden sub-graph structure)刻劃，以及線圖(line graph)的刻劃。同時得到與集合系統表示唯一性等相關結果。近期與印?Cochin University的Dr. Ambat Vijayakumar共同研究此方向，獲得graph product研究成果。本計畫亦將研究相關的圖集合表示(set representation)的唯一性問題。
This project studies the graph labeling, graph coloring, graph partition, and graph covering. We will research on the following related topics using the tools from finite geometry, number theory, group theory, and other standard combinatorial methods: ? Graph labeling of distance two conditions, or L(2,1)-labeling, is an assignment of non-negative integers to vertices, such that the labels are distinct for vertices with distance at most two, and the difference of labels is at least two for adjacent vertices. One of our goals in this project is to study the Griggs-Yeh Conjecture. ? An antimagic labeling of a given graph with p vertices and q edges, is a bijection of the set of 1,2,….,q to the edge set such that all vertex sums are pairwise distinct, where the vertex sum on a vertex is the sum of edge labels incident to such vertex. Nora Hartsfield and Gerhard Ringel made a conjecture that all connected graphs except the K2 admit antimagic labeling. In 2004 Noga Alon et al. showed by this conjecture is true for dense graphs. We are going to study sparse graphs which admit such labeling, and try to provide with more insights to solve the Hartsfield-Ringel conjecture. ? Let (Zk, +, 0) be the finite cyclic additive group consisting of congruence classes modulo k > 1. An edge labeling using nonzero elements in Zk is call Zk-magic if all associated vertex sums are constant. To characterize Zk-magic graphs is quite hard. We will study the magic sum spectrum of various classes of graphs. ? Choosability problems are natural generalizations of coloring problems. We will study the related problems about Steinberg Conjecture in this project. ? The edge clique covering (clique partition, respectively) problem is that for a given graph, to find the least number of cliques so that every edge is contained in at least (exactly, respectively) one clique. Fred Roberts and Walter Wallis considered the class of graphs for which the set of all maximal cliques forms an edge clique covering of minimum size, which is called maximal clique irreducible graphs. We study a general class weakly maximal clique irreducible graphs, which is the subject of recent collaboration with Dr. Vijayakumar in Cochin University in India. We also study related subjects regarding the uniqueness of set representations of graphs. |
