The competition graphs of multipartite tournaments

Abstract

The competition graph C(D) of a digraph D is the (simple undirected) graph, which has the same vertex set as D and has an edge between two distinct vertices u and v if the arcs (u, x) and (v, x) are in D for some vertex x in V (D). Since Cohen introduced the notion of competition grapsh while studying predator-prey concepts in ecological food webs, there has been a lot of research in the area of competition graphs. Recently, Kim et al. studied the competition graph of an oriented complete bipartite graph. In this thesis, we extend their work to study the competition graph of multipartite tournament which is an orientation of a complete multipartite graph. We study multipartite tournaments whose competition graphs are complete. In addition, we characterize connected triangle-free competition graphs of tripartite tournaments. Finally, we study the structure of the competition graphs of multipartite tournaments in the aspect of sink sequences.

유향그래프 D의 경쟁그래프 C(D)는 D와 같은 꼭짓점 집합을 갖고 어떤 꼭짓점 x에 대하여 유향변(u, x)와 (v, x)가 D에 존재하면 2개의 서로 다른 꼭짓점 u와 v사이의 변을 갖는 방향이 없는 단순 그래프이다. Cohen(1968)은 생태계의 먹이사슬에서 포식자-피식자 개념을 연구하면서 경쟁그래프의 개념을 고안하였고, 경쟁그래프의 분야에서 많은 연구가 있어왔다. 최근, Kim(2016)은 방향 지어진 완전 이분그래프의 경쟁그래프를 연구하였다. 이 논문에서는 그 결과를 확장하여 완전 다분 그래프에 방향을 부여한 방향지어진 완전 다분 그래프의 경쟁 그래프를 연구하였다. 먼저 방향 지어진 완전 다분 그래프의 경쟁 그래프가 완전 그래프가 되는 경우에 대하여 연구하였다. 또한 경쟁그래프로 연결되고 삼각형을 포함하지 않는 그래프를 갖는 방향 지어진 완전 삼분그래프를 특징화하였다. 마지막으로 방향 지어진 완전 다분 그래프의 경쟁 그래프의 구조를 sink 수열의 관점에서 연구하였다.