圖的競爭值

Abstract

Cohen 在1968年時研究生態系統而首先定義了有向圖的競爭圖。一無圈有向圖D 的競 爭圖是一無向圖G ，其點集V(G)=V(D) ，其邊集E(G)包含所有邊xy，在點集V(D)中存 在點Z 使得有向邊xz和yz在邊集E(D)中。圖G 的競爭值是使得G 加上k 個新的獨立點 成為某無圈有向圖的競爭圖的最小非負整數k. Roberts也研究了這方面的問題，並且 決定了不含三角圖的圖的競爭值。在這篇論文中，我們要決定一些含有三角圖的圖的 競爭值，例如m 一輪，點圖和圖的卡氏積及完全三分圖。