Publications
Detailed Information
A study on competition numbers of planar graphs
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Advisor
- 김서령
- Major
- 사범대학 수학교육과
- Issue Date
- 2016-02
- Publisher
- 서울대학교 대학원
- Keywords
- competition graph ; competition number ; edge clique cover number ; effective competition cover ; primary predator index ; planar graph
- Description
- 학위논문 (석사)-- 서울대학교 대학원 : 수학교육과, 2016. 2. 김서령.
- Abstract
- 임의의 그래프의 경쟁수를 계산하는 것은 NP-Hard 문제이다. 그래프 G의 경쟁수에 대한 상계 M을 구하는 것은 그래프 G에 M개의 고립점을 더한 것을 경쟁그래프로 가지는 비순환 유향그래프 D를 직접 구성함으로써 보일 수 있다. 반면, 하계를 구하는 것은 매우 많은 경우를 고려해야 하기 때문에 어려운 일이다.
이 논문에서는 그래프 $G$의 최상위 포식자 지수 p(G)를 도입하여 Opsut(1982)이 제시한 경쟁수에 대한 하계보다 일반화된 새로운 하계를 제시하고, 이것이 `효율적인 경쟁 덮개'를 가지는 그래프의 경쟁수와 일치함을 보였다. 또한 다이아몬드를 갖지 않는 연결된 평면 그래프의 경쟁수를 최상위 포식자 지수를 이용하여 표현하고 이중 특정 평면그래프의 경쟁수를 계산하였다.
- Language
- Korean
- Files in This Item:
- Appears in Collections:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.