相交圖相關問題之研究

Abstract

本篇論文，我們主要是探討與研究相交圖理論的三個分支，其中包含圖的點團覆蓋(分割)，圖的點積表示法及競爭圖。 首先在第二章中，我們研究關於線圖的點團覆蓋(分割)。對於由McGuinness和Rees [41]所獲得關於線圖的點團覆蓋(分割)之結果，我們提供一致性說法證明之。我們使用此證明技巧對於De Brujin-Erdős定理給一個簡易的證明。 接著在第三章與第四章中，我們研究關於圖的點積表示法問題。在1998年，Fiduccia等人[16]首先提出圖的點積表示法問題。他們証明ρ(Kn, n)＝n和猜測對於所有具有n個頂點的圖G都滿足ρ(G)≦ 。在第三章，我們針對這個猜測給予部份結果。其次，我們定義緊密相關的概念，即是圖的(嚴格)強點積表示法。在第四章中，我們學習關於圖的(嚴格)強點積表示法的概念。 最後在第五章至第八章中，我們研究關於競爭圖的問題。Roberts [50]證明弦圖的競爭數最多是一。Cho和Kim[8]證明恰有一個洞的圖的競爭數最多是二。任給二個正整數h和k滿足k≦h+1，Kim [30]找到一個恰有h個洞的連通圖使得滿足其競爭數為k。緊接著他提出一個問題：所有恰有h個洞的圖的競爭數是否皆小於或等於h+1？當h≦1時，這個答案是正確。在第五章中，我們證明所有恰有h個獨立洞的圖的競爭數皆小於或等於h+1。接著在第六章中，我們證明當h＝2時，此問題的答案是正確。 在第七章中，我們回顧關於比賽圖的控制圖的己知結果。其次，探討並刻劃當一個具有``零到全'性質的比賽圖的性質。我們也研究比賽圖的k-控制圖的著色問題。最後，在第八章中我們研究比賽圖的競爭圖與競爭超越圖的著色問題。

This dissertation focuses on the study of three topics in intersection graph theory: clique coverings (partitions) of graphs, dot product representations of graphs and competition graphs. We first study clique coverings (partitions) of line graphs in Chapter 2. This chapter gives alternative proofs, using a unified approach, for the results on the clique covering (partition) numbers of line graphs obtained by McGuinness and Rees [41]. We also employ the proof techniques to give an alternative proof for the De Brujin-ErdH{o}s Theorem. We next study the dot product representation problem, which was introduced by Fiduccia et al. [16] in 1998, in Chapters 3 and 4. They showed that $ ho(K_{n,n})=n$ and conjectured that for all graphs G of n vertices,$ ho(G)leqfrac{n}{2}$. Chapter 3 gives partial solutions to this conjecture. We then define the closely related notions of (strict) strong dot product representation. Chapter 4 studies (strict) strong dot product representations. Finally, we investigate the competition graphs in Chapters 5 through 8. Roberts [50] proved that the competition number of a chordal graph is at most one. Cho and Kim [8] established that the competition number of a graph with exactly one hole is at most two. Given two positive integers h and k with $kleq h+1$, Kim [30] constructed a connected graph G with exactly h holes and $kappa(G)=k$. Then he asked the question: Is h+1 the maximum competition number of a graph with exactly $h$ holes? The answer is yes for $hleq 1$. We first show that the competition number of a graph with exactly h holes, all of which are independent, is at most h+1 in Chapter 5. Next, Chapter 6 proves the answer of this question is yes for h=2. In Chapter 7, we review some results on domination graphs of tournaments. We characterize a tournament that satisfies the empty-to-complete property. We also study coloring on k-domination graphs of tournaments. Chapter 8 studies coloring on competition graphs and competition hypergraphs of tournaments.