本研究計畫為期 3 年，有3 個主要研究課題。本研究計畫的第一部份，屬於代數圖論的範疇，處理圖上的零度問題 (nullity problem) 與最小秩問題(minimum rank problem)。在零度問題方面，主要處理下列問題： 1. 刻劃滿足 r(G)=5 的這類圖。 2. 刻劃滿足r(G)=6 的bipartite graph G。 3. 將圖G 限制在特殊圖上，刻劃滿足η(G) > 0 的圖類G。 4. 刻劃滿足η(L(T)) = 1 的樹T, 其中L(T)為樹T 的線圖(line graph)。在最小秩問題方面，主要處理下列問題： 1. 對Hamming graphs 這類圖求minimum rank 與zero forcing number。 2. 對一個圖G 的line graph L(G)與total graph T(G)，研究minimum rank 與zero forcing number。 3. 解析AIM minimum rank workshop 在2006 年提出的Delta Conjecture。 4. 在特殊圖上研究Graph Complement Conjecture。 5. 有系統的研究minimum rank of full sign patterns，及詳細探討其在電腦通訊複雜度上的應用。本研究計畫的第二部份，在探討社交網路(social network)上的擴散問題(diffusion problem)。研究「網路世界裡的口碑行銷」(Word-of-Mouth)、「電腦病毒感染散播」，「流行病傳播」、「人群中政治耳語謠言的傳播」、「森林大火蔓延的控制」…等離散動態系統的基本數學模型。本研究計畫的第三部份，在處理圖型上的著色問題，主要處理circular chromatic number 與下面兩個重要且困難的猜測：Dichotomy Conjecture for Digraph Homomorphism 及 Dichotomy Conjecture for CSP。 The purpose of this project has three parts. In the first part, we study graph nullity problems and minimum rank problems. We focus on the following problems: 1. Give a complete characterization of graphs having rank 5. 2. Give a complete characterization of bipartite graphs having rank 6. 3. Study singular graphs. 4. Study η(L(T)), where L(T) is the line graph of tree T. 5. Study minimum rank and zero forcing number for Hamming graphs. 6. Study Delta Conjecture and Graph Complement Conjecture. 7. Study minimum rank of full patterns and its applications in communication complexity. In the second part, we study diffusion problem on social network. In the third part of the project, we deal with circular chromatic number and study Dichotomy Conjecture for Digraph Homomorphism and Dichotomy Conjecture for CSP 研究期間：10008 ~ 10107
