The trees which are m-step competition graphs of digraphs with a source

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.

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인 점을 갖는 유향 그래프의 개수를 구하였다.