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 graphcompetition numberedge clique cover numbereffective competition coverprimary predator indexplanar graph
Description
학위논문 (석사)-- 서울대학교 대학원 : 수학교육과, 2016. 2. 김서령.
Abstract
임의의 그래프의 경쟁수를 계산하는 것은 NP-Hard 문제이다. 그래프 G의 경쟁수에 대한 상계 M을 구하는 것은 그래프 G에 M개의 고립점을 더한 것을 경쟁그래프로 가지는 비순환 유향그래프 D를 직접 구성함으로써 보일 수 있다. 반면, 하계를 구하는 것은 매우 많은 경우를 고려해야 하기 때문에 어려운 일이다.

이 논문에서는 그래프 $G$의 최상위 포식자 지수 p(G)를 도입하여 Opsut(1982)이 제시한 경쟁수에 대한 하계보다 일반화된 새로운 하계를 제시하고, 이것이 `효율적인 경쟁 덮개'를 가지는 그래프의 경쟁수와 일치함을 보였다. 또한 다이아몬드를 갖지 않는 연결된 평면 그래프의 경쟁수를 최상위 포식자 지수를 이용하여 표현하고 이중 특정 평면그래프의 경쟁수를 계산하였다.
Language
Korean
URI
https://hdl.handle.net/10371/127611
Files in This Item:
Appears in Collections:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share