演講訊息 TALKS

Given an acyclic digraph D, the competition graph C(D) of D is the graph with the same vertex set with D where two vertices x and y are adjacent in C(D) if and only if there is a vertex v in D such that (x, v) and (y, v) are arcs of D. It can be shown that any graph G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. For a given graph G, the competition number of G, denoted κ(G), is the smallest number r such that G ∪ Ir is the competition graph of an acyclic digraph. In this talk, I will introduce some previous works about this problem.