A study on competition numbers of planar graphs

학위논문 (석사)-- 서울대학교 대학원 : 수학교육과, 2016. 2. 김서령.임의의 그래프의 경쟁수를 계산하는 것은 NP-Hard 문제이다. 그래프 G의 경쟁수에 대한 상계 M을 구하는 것은 그래프 G에 M개의 고립점을 더한 것을 경쟁그래프로 가지는 비순환 유향그래프 D를 직접 구성함으로써 보일 수 있다. 반면, 하계를 구하는 것은 매우 많은 경우를 고려해야 하기 때문에 어려운 일이다. 이 논문에서는 그래프 $G$의 최상위 포식자 지수 p(G)를 도입하여 Opsut(1982)이 제시한 경쟁수에 대한 하계보다 일반화된 새로운 하계를 제시하고, 이것이 `효율적인 경쟁 덮개'를 가지는 그래프의 경쟁수와 일치함을 보였다. 또한 다이아몬드를 갖지 않는 연결된 평면 그래프의 경쟁수를 최상위 포식자 지수를 이용하여 표현하고 이중 특정 평면그래프의 경쟁수를 계산하였다.Chapter 1 Introduction 1 Chapter 2 Effective competition covers of graphs 6 Chapter 3 Relationship between the competition number and the primary predator index of a graph 13 Chapter 4 Competition numbers of planar graphs 20 Chapter 5 Concluding remarks 38 Bibliography 39 국문초록 42Maste