Browse

A study on the competition graphs of d-partial orders : d-반순서의 경쟁그래프의 연구

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors

최지훈

Advisor
김서령
Major
사범대학 수학교육과
Issue Date
2018-02
Publisher
서울대학교 대학원
Keywords
competition graphsd-partial orderspartial order competition dimensionhomothetic regular simplicesorder types
Description
학위논문 (박사)-- 서울대학교 대학원 : 사범대학 수학교육과, 2018. 2. 김서령.
Abstract
The \emph{competition graph} $C(D)$ of a digraph $D$ is defined to be a graph whose vertex set is the same as $D$ and which has an edge joining two distinct vertices $x$ and $y$ if and only if there are arcs $(x,z)$ and $(y,z)$ for some vertex $z$ in $D$. Competition graphs have been extensively studied for more than four decades.

Cohen~\cite{cohen1968interval, cohen1977food, cohen1978food} empirically observed that most competition graphs of acyclic digraphs representing food webs are interval graphs. Roberts~\cite{roberts1978food} asked whether or not Cohen's observation was just an artifact of the construction, and then concluded that it was not by showing that if $G$ is an arbitrary graph, then $G$ together with additional isolated
vertices as many as the number of edges of $G$ is the competition graph of some acyclic digraph. Then he asked for a characterization of acyclic digraphs whose competition graphs are interval graphs. Since then, the problem has remained elusive and it has been one of the basic open problems in the study of competition graphs. There have been a lot of efforts to settle the problem and some progress has been made. While Cho and Kim~\cite{cho2005class} tried to answer his question, they could show that the competition graphs of doubly partial orders are interval graphs. They also showed that an interval graph together with sufficiently many isolated vertices is the competition graph of a doubly partial order.

In this thesis, we study the competition graphs of $d$-partial orders some of which generalize the results on the competition graphs of doubly partial orders.

For a positive integer $d$, a digraph $D$ is called a \emph{$d$-partial order} if $V(D) \subset \RR^d$ and there is an arc from a vertex $\mathbf{x}$ to a vertex $\mathbf{y}$ if and only if $\mathbf{x}$ is componentwise greater than $\mathbf{y}$. A doubly partial order is a $2$-partial order.

We show that every graph $G$ is the competition graph of a $d$-partial order for some nonnegative integer $d$, call the smallest such $d$ the \emph{partial order competition dimension} of $G$, and denote it by $\dim_\text{poc}(G)$.
This notion extends the statement that the competition graph of a doubly partial order is interval and the statement that any interval graph can be the competition graph of a doubly partial order as long as sufficiently many isolated vertices are added, which were proven by Cho and Kim~\cite{cho2005class}. Then we study the partial order competition dimensions of some interesting families of graphs. We also study the $m$-step competition graphs and the competition hypergraph of $d$-partial orders.
Language
English
URI
https://hdl.handle.net/10371/140870
Files in This Item:
Appears in Collections:
College of Education (사범대학)Dept. of Mathematics Education (수학교육과)Theses (Ph.D. / Sc.D._수학교육과)
  • mendeley

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

Browse