How Will Competition Numbers Change by One-Edge Manipulations?

Abstract

In this thesis, we investigate the competition graph and the competition number. Kim's conjecture and the related theorems are summarized and the proof of Kim's conjecture which was done in 2011 is presented.

There are three main results in this thesis. First, we show how the competition number is changed when some condition is given to a graph with cut-edge. Secondly, we investigate the condition under which the competition of a digraph is changed when an edge is added to its competition graph. Finally, we find a sufficient condition which increases the competition number by one.

이 논문에서는 경쟁그래프 및 경쟁수에 관한 전반적인 고찰을 하였고, Kim's conjecture 및 그와 관련된 여러 정리들을 살펴보았다. 또한 2011년 10월에 발표된 Kim's conjecture의 증명법을 간단히 소개하였다. 논문의 주된 결과(main result)는 세 가지인데 첫째, cut-edge를 가지고 있는 그래프에 세부적인 조건을 주었을 때의 경쟁수를 고찰하고 증명하였다. 두 번째로 이분그래프에서 한 변을 추가하였을 때 경쟁수가 늘어나고 줄어드는 경우를 살펴보고 구체적인 경쟁수를 계산 및 증명하였다. 세 번째로 경쟁수가 1이 되는 충분조건을 하나 찾아내었다.