The trees which are m-step competition graphs of digraphs with a source
내차수가 0인 점을 갖는 유향 그래프의 m-step 경쟁 그래프인 수형도

Cited 0 time in Web of Science Cited 0 time in Scopus
Issue Date
서울대학교 대학원
treestar graphm-step competition graphtree-inducing digraphidel vertex
학위논문(석사)--서울대학교 대학원 :사범대학 수학교육과,2019. 8. 김서령.
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.
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인 점을 갖는 유향 그래프의 개수를 구하였다.
Files in This Item:
Appears in Collections:
College of Education (사범대학)Dept. of Mathematics Education (수학교육과)Theses (Master's Degree_수학교육과)
  • mendeley

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