完全雙分圖中的二競爭圖

Abstract

一個有向圖D 的二競圖定義如下: 二競爭圖的點集合等於原有向圖的 集 合，點x 和點y 有邊相連若且唯若存在不同兩點V_1，V_2使得 xV_1， V_2，yV_1，yV_2 都是有向圖的弧。在這篇論文中，我們將研究什麼時後 K_{3,x}會是某個有向圖的二競圖，什麼時候又不是。 The 2-competition graph of a digraph D = (V(D),A(D)) is theraph C_2(D) = (V(C_2(D),E(C_2(D))) with V(C_2(D)) = V(D) and_2(D)) = {xy: there are two distinct vertices V_1,V_2.in.V(D) such that xV_1,xV_2,yV_1,yV_2.in.A(D)}. In this thesis, we studyhe problem of determining if K_{3,x} is a 2-competition graph ofome digraph or not.