Publications
Detailed Information
The trees which are m-step competition graphs of digraphs with a source : 내차수가 0인 점을 갖는 유향 그래프의 m-step 경쟁 그래프인 수형도
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | 김서령 | - |
dc.contributor.author | 최명호 | - |
dc.date.accessioned | 2019-10-18T16:58:24Z | - |
dc.date.available | 2019-10-18T16:58:24Z | - |
dc.date.issued | 2019-08 | - |
dc.identifier.other | 000000157072 | - |
dc.identifier.uri | https://hdl.handle.net/10371/161333 | - |
dc.identifier.uri | http://dcollection.snu.ac.kr/common/orgView/000000157072 | ko_KR |
dc.description | 학위논문(석사)--서울대학교 대학원 :사범대학 수학교육과,2019. 8. 김서령. | - |
dc.description.abstract | Cohen [1] introduced the notion of competition graph while studying predator-prey concepts in ecological food webs.
Among the variants of competition graphs, the notion of m-step competition graph to be studied in this thesis, was introduced by Cho et al. [2]. In 2000, Cho et al. [2] posed the following question: For which values of m and n is P_n an m-step competition graph? Helleloid [4] and Kuhl et al. [5] partially answered the question in 2005 and 2010, respectively. In 2011, Belmont [6] presented a complete characterization of paths that are m-step competition graphs. In this thesis, we study ``tree-inducing digraphs" with a source. We call a digraph D with at least three vertices an m-step tree-inducing digraph if the m-step competition graph of D is a tree for some integer m greater than or eqaul to 2. We say that a digraph is a tree-inducing digraph if it is an m-step tree-inducing digraph for some integer m greater than or eqaul to 2. We first completely characterize a tree-inducing digraph with a source. Interestingly, it turns out that if a tree is the m-step competition graph of a digraph with a source, then it is a star graph. We also compute the number of tree-inducing digraphs with a source. | - |
dc.description.abstract | Cohen(1968)은 생태계의 먹이사슬에서 포식자-피식자 개념을 연구하면서 경쟁그래프의 개념을 고안하였다.
Cho 외(2000)은 경쟁그래프의 많은 변형들 중의 하나로서 m-step 경쟁그래프라는 개념을 만들어 내었고 P_n이 m-step 경쟁그래프가 될 수 있는 m과 n에 대한 문제를 제기하였다. Helleloid(2005)와 Kuhl 외(2010)은 이 문제에 대한 부분적인 답을 제시하였다. Belmont(2011)는 m-step 경쟁그래프인 패스에 대하여 완벽하게 규명하였다. 이 논문에서는 내차수가 0인 점을 갖는 수형도 유발 유향그래프에 대하여 연구하였다. 점을 3개 이상을 갖는 유향그래프 D가 2이상의 어떤 정수 m에 대한 m-step 경쟁그래프가 수형도일 때, D를 m-step 수형도 유발 유향그래프라고 부른다. m-step 수형도 유발 유향그래프를 수형도 유발 유향그래프라고 부른다. 우선, m-step 경쟁그래프가 수형도인 내차수가 0인 점을 갖는 유향 그래프의 구조를 완전하게 규명하였다. 흥미롭게도, 내차수가 0인 점을 갖는 유향 그래프의 m-step 경쟁그래프가 수형도일 때는 항상 별 그래프임을 보였다. 최종적으로는 m-step 경쟁그래프가 수형도인 내차수가 0인 점을 갖는 유향 그래프의 개수를 구하였다. | - |
dc.description.tableofcontents | Abstract
1. Introduction. 1.1 Basic graph terminology - 1 -. 1.2 Competition graph and its variants - 3 -. 1.3 m-step competition graphs - 4 -. 2. Tree-inducing digraphs 2.1 Some properties of tree-inducing digraphs - 6 -. 2.2 An idle vertex of a tree-inducing digraph - 10 -. 3. Tree-inducing digraphs with a source 3.1 A characterization of tree-inducing digraphs with a source - 19 -. 3.2 The number of tree-inducing digraphs with a source - 24 -. Bibliography - 28 -. Abstract (in Korean) - 32 -. Acknowledgement (in Korean) - 33 -. | - |
dc.language.iso | eng | - |
dc.publisher | 서울대학교 대학원 | - |
dc.subject | tree | - |
dc.subject | star graph | - |
dc.subject | m-step competition graph | - |
dc.subject | tree-inducing digraph | - |
dc.subject | idel vertex | - |
dc.subject.ddc | 510.7 | - |
dc.title | The trees which are m-step competition graphs of digraphs with a source | - |
dc.title.alternative | 내차수가 0인 점을 갖는 유향 그래프의 m-step 경쟁 그래프인 수형도 | - |
dc.type | Thesis | - |
dc.type | Dissertation | - |
dc.contributor.AlternativeAuthor | Myungho Choi | - |
dc.contributor.department | 사범대학 수학교육과 | - |
dc.description.degree | Master | - |
dc.date.awarded | 2019-08 | - |
dc.identifier.uci | I804:11032-000000157072 | - |
dc.identifier.holdings | 000000000040▲000000000041▲000000157072▲ | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.