p-row graphs and p-competition graph

Abstract

For a positive integer $p$, the $p$-competition graph of a digraph $D$ is a graph which has the same vertex set as $D$ and an edge between distinct vertices $x$ and $y$ if and only if $x$ and $y$ have at least $p$ common out-neighbors in $D$. A graph is said to be a $p$-competition graph if it is the $p$-competition graph of a digraph. In this paper, we introduce { the notions of $p$-row graph of a matrix and competition-realizer for a graph} to study $p$-competition graphs. {Using these notions}, we study the competition-realizers of various graphs to extend results given by Kim {\it et al.}~[$p$-competition graphs, {\it Linear Algebra Appl.} {\bf 217} (1995) 167--178]. Especially, we completely characterize the competition-realizers for caterpillars.

양의 정수 $p$에 대해, 어떤 유향그래프 $D$의 $p$-경쟁그래프는 꼭짓점의 집합을 $D$와 같이 갖고 두 꼭짓점 $x$와 $y$가 변으로 이어질 필요충분조건을 $x$와 $y$가 최소한 $p$개 이상의 공통된 외이웃을 가지는 것으로 하는 그래프로 정의된다. 어떤 그래프 $G$에 대해 어떤 유향그래프 $D$가 존재해서 $G$가 $D$의 $p$-경쟁그래프가 될 때 $G$를 $p$-경쟁그래프라고 부른다. 그래프 $G$가 주어졌을 때, $G$가 $p$-경쟁그래프가 되는 양의 정수 $p$의 집합을 $G$의 경쟁실현집합이라고 정의한다. 그래프 $G$에 대해서 서로 같은 닫힌 외이웃을 갖는 인접한 꼭짓점을 동일시하여 얻은 그래프를 $G/\!\!\sim$으로 나타낸다. 본 연구에서는 기존의 행그래프에 대한 개념을 확장한 $p$-행그래프를 도입하였고, $p$-행그래프와 $G/\!\!\sim$을 이용하여 다양한 그래프의 경쟁실현집합을 찾아내었으며 기존의 연구에서 나왔던 결과들을 확장하였으며 수형도의 일종인 캐터필러의 경쟁실현집합의 모든 원소를 찾아내었다.