# Competition graphs of degree bounded digraphs

Hojin Chu  Department of Mathematics Education, Seoul National University,
Seoul 08826, Rep. of Korea Suh-Ryung Kim  Department of Mathematics Education,
Seoul National University, Seoul 08826, Rep. of Korea

###### Abstract

If each vertex of an acyclic digraph has indegree at most $i$ and outdegree at
most $j$, then it is called an $(i,j)$ digraph, which was introduced by Hefner
et al. (1991). Whereas Hefner et al. characterized $(i,j)$ digraphs whose
competition graphs are interval, characterizing the competition graphs of
$(i,j)$ digraphs is not an easy task. In this paper, we introduce the concept
of $\langle i,j\rangle$ digraphs, which relax the acyclicity condition of
$(i,j)$ digraphs, and study their competition graphs. By doing so, we obtain
quite meaningful results. Firstly, we give a necessary and sufficient
condition for a loopless graph being an $\langle i,j\rangle$ competition graph
for some positive integers $i$ and $j$. Then we study on an $\langle
i,j\rangle$ competition graph being chordal and present a forbidden subdigraph
characterization. Finally, we study the family of $\langle i,j\rangle$
competition graphs, denoted by $\mathcal{G}_{\langle i,j\rangle}$, and
identify the set containment relation on $\\{\mathcal{G}_{\langle
i,j\rangle}\colon\,i,j\geq 1\\}$.

Keywords. Competition graph; $\langle i,j\rangle$ digraph; Chordal; Balanced
incomplete block design.

2020 Mathematics Subject Classification. 05C20, 05C75

##  1 Introduction

In this paper, all the digraphs are assumed to have neither loops nor parallel
arcs. For all undefined graph-theoretical terminology, we follow [1].

In 1968, Cohen [2] introduced the notion of competition graphs in connection
with competition in the food web of ecosystems. Given a digraph $D$, the
competition graph of $D$, denoted by $C(D)$, has the same vertex set as $D$
and an edge $uv$ if and only if $u$ and $v$ have a common out-neighbor in $D$.
A competition graph of a digraph is simple. In this vein, all the graphs are
assumed to be simple throughout the paper. The competition graph has various
applications in coding, radio transmission, and modeling of complex economic
systems and its variants were introduced and have been studied (see [3],
[4],[5],[6],[7],[8], [9]). Especially, we note that [8] and [9] are research
results derived from recent studies on phylogeny graph, which is a variant of
competition graph, of a degree bounded digraph.

When Cohen introduced the notion of competition graphs, he observed that most
food web is acyclic, that is, there is no directed cycle in the digraph
modeled by the food web. Thus mostly competition graphs of acyclic digraphs
were studied in the early stages of research. In 1982, Opsut [10] showed that
the problem of determining whether or not an arbitrary graph is the
competition graph of some acyclic digraph is NP-complete. Since it is not easy
to characterize the competition graphs of acyclic digraphs in general,
researchers have been attempted to study the competition graphs of restricted
acyclic digraphs or arbitrary digraphs. For example, Dutton and Brigham [11]
characterized the competition graphs of arbitrary digraphs. Roberts and Steif
[12] characterized the competition graphs of loopless digraphs. Lundgren and
Maybee [13] characterized the graphs which can be made into the competition
graphs of acyclic digraphs by adding $m$ isolated vertices but it is not
possible to be the competition graphs of acyclic digraphs if less than $m$
isolated vertices are added. While Hefner et al. [14] characterized certain
degree bounded acyclic digraphs whose competition graphs are interval, it is
not easy to characterize even the competition graphs of degree bounded acyclic
digraphs. In this paper, we characterize the competition graphs of degree
bounded loopless digraphs.

In 1991, Hefner et al. introduced the notion of $(i,j)$ digraphs and studied
the competition graphs of $(i,j)$ digraphs. The $(i,j)$ digraph is an acyclic
digraph such that $d^{-}(x)\leq i$ and $d^{+}(x)\leq j$ for every vertex $x$,
where $d^{-}(x)$ and $d^{+}(x)$ denote the indegree and the outdegree of a
vertex $x$, respectively. We expand the notion of $(i,j)$ digraphs by allowing
some directed cycles and call it an $\langle i,j\rangle$ digraph. The $\langle
i,j\rangle$ digraph is a loopless digraph satisfying $d^{-}(x)\leq i$ and
$d^{+}(x)\leq j$ for every vertex $x$. By definition, an $\langle i,j\rangle$
digraph might not be acyclic. We say that a graph is an $\langle i,j\rangle$
competition graph if it is the competition graph of some $\langle i,j\rangle$
digraph. By definition, note that an $\langle i,j\rangle$ competition graph is
a $\langle k,l\rangle$ competition graph for each integers $i$, $j$, $k$, and
$l$ satisfying $i\leq k$ and $j\leq l$.

In Section 2, we give necessary and sufficient conditions for a loopless graph
being an $\langle i,j\rangle$ competition graph for some positive integers $i$
and $j$ (Theorems 2.2 and 2.7). We also deduce an interesting fact that the
existence of certain $\langle i,j\rangle$ competition graph is equivalent to
the existence of a balanced incomplete block design for some variables
(Proposition 2.8). In addition, we give a sufficient condition for an $\langle
i,j\rangle$ competition graph being chordal in the aspect of subdigraph
restriction (Proposition 2.10). Especially, it becomes a necessary and
sufficient condition when $j=2$ (Theorem 2.11). In Section 3, we denote the
family of $\langle i,j\rangle$ competition graphs by $\mathcal{G}_{\langle
i,j\rangle}$ and take a look at set containment between $\mathcal{G}_{\langle
i,j\rangle}$ and $\mathcal{G}_{\langle k,l\rangle}$ for given positive
integers $i$, $j$, $k$, and $l$ with $(i,j)\neq(k,l)$ (Theorem 3.1). To show
$\mathcal{G}_{\langle i,j\rangle}\not\subseteq\mathcal{G}_{\langle
k,l\rangle}$ for specific $i$, $j$, $k$, and $l$, we use quite novel idea to
construct a graph belonging to $\mathcal{G}_{\langle i,j\rangle}$ but not
belonging to $\mathcal{G}_{\langle k,l\rangle}$ (Propositon 3.6).

##  2 $\langle i,j\rangle$ competition graphs

Given a graph $G$, a clique $C$ is a subgraph of $G$ in which any two vertices
are adjacent. If there is no possibility of confusion, we will use the same
symbol “C” for the set of vertices of C. An edge clique cover of a graph $G$
is the collection of cliques in $G$ that covers all the edges in $G$.

Let $A$ be a finite set and let $\mathcal{A}=\\{A_{1},\ldots,A_{m}\\}$ be a
collection of subsets of $A$. A system of distinct representatives (SDR) of
$\mathcal{A}$ is a collection of distinct elements $a_{1},\ldots,a_{m}$ such
that $a_{i}\in A_{i}$ for each $1\leq i\leq m$.

Roberts and Steif gave a necessary and sufficient condition for a graph being
the competition graph of a loopless digraph as follows.

######  Theorem 2.1 (Roberts and Steif[12]).

A graph $G$ is the competition graph of a digraph which has no loop if and
only if there is an edge clique cover $\\{C_{1},C_{2},\ldots,C_{p}\\}$ of $G$
such that $\\{V(G)-C_{1},V(G)-C_{2},\ldots,V(G)-C_{p}\\}$ has a system of
distinct representatives.

An $\langle i,j\rangle$ competition graph obviously satisfies the condition
given in the above theorem. As a matter of fact, it satisfies three more
conditions stated in the following theorem and those four conditions in the
theorem are actually sufficient to guarantee that a graph is an $\langle
i,j\rangle$ competition graph.

######  Theorem 2.2.

A graph $G$ is an $\langle i,j\rangle$ competition graph for some positive
integers $i$ and $j$ if and only if there is an edge clique cover
$\mathcal{C}=\\{C_{1},\ldots,C_{p}\\}$ of $G$ satisfying the following
conditions:

  1. (i)

$|C_{t}|\leq i$ for each $1\leq t\leq p$;

  2. (ii)

each vertex of $G$ belongs to at most $j$ cliques in $\mathcal{C}$;

  3. (iii)

$\\{V(G)-C_{1},\ldots,V(G)-C_{p}\\}$ has an SDR;

  4. (iv)

$p\leq|V(G)|$.

###### Proof.

To show the “only if” part, suppose that $G$ is the competition graph of an
$\langle i,j\rangle$ digraph $D$. Let $\mathcal{C}=\\{N^{-}_{D}(v)\colon\,v\in
V(D)\text{ with
}N^{-}_{D}(v)\neq\emptyset\\}=\\{N^{-}_{D}(v_{1}),\ldots,N^{-}_{D}(v_{p})\colon\,v_{1},\ldots,v_{p}\in
V(D)\\}$. By the definition of competition graph, $\mathcal{C}$ is an edge
clique cover of $G$. By the fact that $G$ is an $\langle i,j\rangle$
competition graph, $\mathcal{C}$ satisfies the conditions (i) and (ii).
Moreover, since $D$ is loopless, $\\{v_{t}\colon\,1\leq t\leq p\\}$ is an SDR
of $\\{V(G)-N^{-}_{D}(v_{t})\colon\,1\leq t\leq p\\}$ and so $\mathcal{C}$
satisfies the condition (iii). Then, by the condition (iii), there are $p$
distinct vertices of $G$, which happen to be distinct representatives. Thus
$p\leq|V(G)|$ and so the condition (iv) holds.

To show the “if” part, suppose that there is an edge clique cover
$\mathcal{C}=\\{C_{1},\ldots,C_{p}\\}$ of given graph $G$ satisfying the
conditions (i), (ii), (iii), and (iv). Let $\\{v_{1},\ldots,v_{p}\\}$ be an
SDR of $\\{V(G)-C_{1},\ldots,V(G)-C_{p}\\}$. Now, we define a digraph $D$ with
the vertex set $V(G)$ and the arc set

$\bigcup_{t=1}^{p}\\{(v,v_{t})\colon\,v\in C_{t}\\}.$

Since $v_{t}\notin C_{t}$ for each $1\leq t\leq p$, $D$ has no loop. Take a
vertex $v$ in $D$. Then $d_{D}^{+}(v)\leq j$ by the condition (ii). If $v\neq
v_{t}$ for any $1\leq t\leq p$, then $N_{D}^{-}(v)=\emptyset$. If $v=v_{t}$
for some $1\leq t\leq p$, then $N_{D}^{-}(v)=C_{t}$ and so $d_{D}^{-}(v)\leq
i$ by the condition (i). Thus $D$ is an $\langle i,j\rangle$ digraph.
Moreover, $u$ and $v$ are adjacent in $G$ if and only if $\\{u,v\\}\subseteq
C_{t}$ for some $1\leq t\leq p$ if and only if $(u,v_{t})$ and $(v,v_{t})$ are
arcs of $D$ for some $1\leq t\leq p$ if and only if $u$ and $v$ are adjacent
in the competition graph of $D$. Therefore the competition graph of $D$ is
$G$. ∎

######  Corollary 2.3.

Let $G$ be an $\langle i,j\rangle$ competition graph for some positive
integers $i$ and $j$. Then the following are true:

(a) $|E(G)|\leq\frac{(i-1)i}{2}|V(G)|$; (b) $G$ is $K_{1,j+1}$-free; (c)
$\Delta(G)\leq j(i-1)$,

where $\Delta(G)$ denotes the maximum degree of $G$, that is, the largest
vertex degree of $G$.

###### Proof.

By Theorem 2.2, there is an edge clique cover
$\mathcal{C}:=\\{C_{1},C_{2},\ldots,C_{p}\\}$ of $G$ which satisfies the
conditions (i), (ii), (iii), and (iv) of the theorem. By the condition (iv),
$p\leq|V(G)|$. Thus

$|E(G)|=\left|\bigcup_{t=1}^{p}E(C_{t})\right|\leq\sum_{t=1}^{p}{|C_{t}|\choose
2}\leq\sum_{t=1}^{p}{i\choose 2}\leq\sum_{t=1}^{|V(G)|}{i\choose
2}=\frac{(i-1)i}{2}|V(G)|$

where the second inequality holds by the condition (i). Therefore (a) holds.

To show (b) by contradiction, suppose that $G$ has an induced subgraph $H$
isomorphic to $K_{1,j+1}$. We denote the center of $H$ by $v$. Then the
neighbors of $v$ in $H$ belong to distinct cliques in $\mathcal{C}$ and so $v$
belongs to at least $j+1$ distinct cliques, which contradicts the condition
(ii).

To show (c), take a vertex $v$. Let $C_{p_{1}},\ldots,C_{p_{s}}$ be the
cliques in $\mathcal{C}$ containing $v$. Then $s\leq j$ by the condition (ii).
Now

$d_{G}(v)=|N_{G}(v)|=\left|\bigcup_{t=1}^{s}(C_{p_{t}}-\\{v\\})\right|\leq\sum_{t=1}^{s}\left(|C_{p_{t}}|-1\right)\leq\sum_{t=1}^{s}\left(i-1\right)\leq
j(i-1)$

where the second inequality holds by the condition (i). Therefore (c) holds. ∎

######  Lemma 2.4.

For each integer $n\geq 3$, a complete graph $K_{n}$ is an $\langle
i,j\rangle$ competition graph if $i\geq n-1$ and $j\geq 2$. Further, $K_{n}$
is not a $\langle k,1\rangle$ competition graph for any integer $k\geq 1$.

###### Proof.

Fix an integer $n\geq 3$. We define a digraph $D$ with the vertex set
$\\{v_{1},\ldots,v_{n}\\}$ and the arc set

$\\{(v_{t},v_{n})\colon\,1\leq t\leq n-1\\}\cup\\{(v_{t},v_{1})\colon\,2\leq
t\leq n\\}\cup\\{(v_{1},v_{2}),(v_{n},v_{2})\\}.$

Then it is easy to see that $D$ is an $\langle n-1,2\rangle$ digraph and its
competition graph is isomorphic to $K_{n}$. Therefore a complete graph $K_{n}$
is an $\langle n-1,2\rangle$ competition graph and so it is an $\langle
i,j\rangle$ competition graph for any integers $i\geq n-1$ and $j\geq 2$.

Let $G$ be the competition graph of a $\langle k,1\rangle$ digraph $D$ of
order $n$ for an integer $k\geq 1$. Take two adjacent vertices $u$ and $v$ in
$G$. Then there is a common out-neighbor $w$ of $u$ and $v$. Since $D$ is a
$\langle k,1\rangle$ digraph without loops, the vertices $u$, $v$, and $w$ are
distinct and

$N_{D}^{+}(u)=N_{D}^{+}(v)=\\{w\\}.$

Thus $u$ and $w$ have no common out-neighbor and hence are not adjacent in
$G$. Therefore a complete graph $K_{n}$ is not a $\langle k,1\rangle$
competition graph for any integer $k\geq 1$. ∎

######  Lemma 2.5 (Roberts and Steif[12]).

Let $k$ be a positive integer and $S_{1},\ldots,S_{k+1}$ be subsets of
$\\{1,\ldots,k\\}$. Then there is an integer $t\in\\{1,2,\ldots,k+1\\}$ such
that $S_{t}\subseteq\bigcup_{i\neq t}S_{i}$.

In Theorem 2.2, the conditions (i), (ii), (iii), and (iv) are given for a
graph to be an $\langle i,j\rangle$ competition graph. However, when
conditions (i), (ii), and (iv) hold, the condition (iii) is equivalent to the
following statement: $G\not\cong K_{2}$ and, if $j=1$, then $G$ is not a
nontrivial complete graph. In this context, for a graph $G$ and positive
integers $i$ and $j$, we denote by $\mathbf{C}(G,i,j)$ the collection of edge
clique cover $\mathcal{C}=\\{C_{1},\ldots,C_{p}\\}$ of $G$ satisfying the
conditions (i), (ii), and (iv) of Theorem 2.2. Then we obtain another
necessary and sufficient condition for a graph to be an $\langle i,j\rangle$
competition graph as follows. To this end, we need Hall’s Marriage Theorem.

######  Theorem 2.6 (Hall[15]).

The family $\mathcal{A}=(A_{1},A_{2},\ldots,A_{n})$ of sets has a system of
distinct representatives if and only if

(Hall’s marriage condition) for each $1\leq k\leq n$ and each choice of $k$
distinct indices $i_{1},i_{2},\ldots,i_{k}$ from $\\{1,2,\ldots,n\\}$,

$\left|A_{i_{1}}\cup A_{i_{2}}\cup\cdots\cup A_{i_{k}}\right|\geq k.$

######  Theorem 2.7.

A graph $G$ is an $\langle i,j\rangle$ competition graph for some positive
integers $i$ and $j$ if and only if (i) $G\not\cong K_{2}$, (ii) $G$ is not a
nontrivial complete graph for $j=1$, and (iii)
$\mathbf{C}(G,i,j)\neq\emptyset$.

###### Proof.

It is easy to see that a complete graph $K_{2}$ cannot be the competition
graph of any digraph unless a loop is allowed. Then the “only if” part is true
by Theorem 2.2 and the “further” part of Lemma 2.4.

To show the “if” part, let $G$ be a graph of order $n$ satisfying the
conditions (i), (ii), and (iii). Let $\mathcal{C}=\\{C_{1},\ldots,C_{p}\\}$ be
an edge clique cover in $\mathbf{C}(G,i,j)$ with the smallest
$w(\mathcal{C}):=\sum_{t=1}^{p}|C_{t}|$. By (iii), $\mathcal{C}$ is well-
defined. If $\sum_{t=1}^{p}|C_{t}|=1$, then $G$ is edgeless and so it is the
competition graph of a digraph $D=(V,\emptyset)$ which is an $\langle
i,j\rangle$ digraph for any positive integers $i$ and $j$.

Suppose $\sum_{t=1}^{p}|C_{t}|>1$. Then $G$ has an edge. If $p=1$ and $G$ has
an isolated vertex $v$, then $G$ is the competition graph of an $\langle
i,j\rangle$ digraph $D$ whose vertex set is $V(G)$ and arc set is

$\\{(u,v)\colon\,u\in C_{1}\\}.$

Consider the case where $p=1$ and $G$ has no isolated vertex. Then $G$ is a
complete graph. Thus $j\geq 2$ and $n\geq 3$ by (i) and (ii). Therefore $G$ is
an $\langle i,j\rangle$ competition graph by Lemma 2.4. Thus we may assume
$p\geq 2$. Then $G$ is not complete since $w(\mathcal{C})$ is the smallest and
no clique in $\mathcal{C}$ is contained in another clique by the choice of
$\mathcal{C}$. We will show that $\mathcal{B}:=\\{B_{1},\ldots,B_{p}\\}$ has
an SDR where $B_{t}=V(G)-C_{t}$ for each $1\leq t\leq p$. Then we are done by
Theorem 2.2.

To the contrary, suppose that $\mathcal{B}:=\\{B_{1},\ldots,B_{p}\\}$ has no
SDR. Then, by Theorem 2.6, there is an nonempty subset
$\\{t_{1},\ldots,t_{s}\\}$ of $\\{1,2,\ldots,p\\}$ satisfying

$B_{t_{1}}\cup\cdots\cup B_{t_{s}}=\\{v_{1},\ldots,v_{l}\\}$

where $v_{1},\ldots,v_{l}$ are vertices of $G$ for some integer $l<s$. Since
$G$ is not complete, $V(G)-C_{t}\neq\emptyset$ for each $1\leq t\leq p$. Thus
$l\geq 1$ and so $s\geq 2$. For each $1\leq a\leq s$,

$C_{t_{a}}\supseteq C_{t_{1}}\cap\cdots\cap
C_{t_{s}}=V(G)-(B_{t_{1}}\cup\cdots\cup
B_{t_{s}})=V(G)-\\{v_{1},\ldots,v_{l}\\}.$

Thus, for each $1\leq a\leq s$, $C_{t_{a}}=(V(G)-\\{v_{1},\ldots,v_{l}\\})\cup
Q_{t_{a}}$ for some $Q_{t_{a}}\subseteq\\{v_{1},\ldots,v_{l}\\}$. Then
$Q_{t_{a}}$ is a subset of $C_{t_{a}}$ which is a clique, so $Q_{t_{a}}$ is
also a clique for each $1\leq a\leq s$. Since $Q_{t_{1}},\ldots,Q_{t_{s}}$ are
subsets of $\\{v_{1},\ldots,v_{l}\\}$ and $s>l$, there is an integer
$r\in\\{1,2,\ldots,s\\}$ such that

$Q_{t_{r}}\subseteq\bigcup_{i\neq r}Q_{t_{i}}$

by Lemma 2.5. Then
$\mathcal{C}^{\prime}:=(\mathcal{C}\setminus\\{C_{t_{r}}\\})\cup\\{Q_{t_{r}}\\}$
belongs to $\mathbf{C}(G,i,j)$. To see why, we first observe that
$\mathcal{C}^{\prime}$ consists of cliques of $G$. For an edge $uv$ in
$C_{t_{r}}$, (1) $\\{u,v\\}\subseteq V(G)-\\{v_{1},\ldots,v_{l}\\}$ or (2)
$u\in V(G)-\\{v_{1},\ldots,v_{l}\\}$ and $v\in Q_{t_{r}}$ or (3) $u\in
Q_{t_{r}}$ and $v\in V(G)-\\{v_{1},\ldots,v_{l}\\}$ (4) $\\{u,v\\}\subseteq
Q_{t_{r}}$. The cases (4) and (1) are taken care of since
$Q_{t_{r}}\in\mathcal{C}^{\prime}$ and $V(G)-\\{v_{1},\ldots,v_{l}\\}\subseteq
C_{t_{a}}$ for $1\leq a\leq s$, respectively. Consider the cases (2) and (3).
Without loss of generality, we may assume that (2) happens. Since
$Q_{t_{r}}\subseteq(Q_{t_{1}}\cup\cdots\cup Q_{t_{s}})-Q_{t_{r}}$, there is an
integer $a\in\\{1,2,\ldots,s\\}$ with $a\neq r$ such that $v\in Q_{t_{a}}$.
Then $v\in C_{t_{a}}$. Since $V(G)-\\{v_{1},\ldots,v_{l}\\}\subseteq
C_{t_{a}}$, $u\in C_{t_{a}}$. Thus the edge $uv$ is covered by
$C_{t_{a}}\in\mathcal{C}^{\prime}$. Therefore $\mathcal{C}^{\prime}$ is an
edge clique cover of $G$. Since $Q_{t_{r}}\subsetneq C_{t_{r}}$,
$\mathcal{C}^{\prime}\in\mathbf{C}(G,i,j)$ and
$w(\mathcal{C}^{\prime})<w(\mathcal{C})$, which contradicts the choice of
$\mathcal{C}$. Hence $G$ is an $\langle i,j\rangle$ competition graph. ∎

We recall some definitions about balanced incomplete block designs. A design
is a pair $(V,\mathcal{B})$ where $V$ is a finite set of varieties and
$\mathcal{B}$ is a collection of subsets of $V$, called blocks of the design.
A balanced incomplete block design (BIBD) is a design consisting of $v$
varieties and $b$ blocks such that each block consists of exactly the same
number $k$ of varieties where $k<v$; each variety appears in exactly the same
number $r$ of blocks; each pair of varieties appears simultaneously in exactly
the same number $\lambda$ of blocks. Such a design is called a
$(b,v,r,k,\lambda)$-BIBD.

The clique number of a graph $G$, denoted by $\omega(G)$, is the number of
vertices in a maximum clique of $G$.

######  Proposition 2.8.

Let $G$ be an $\langle i,j\rangle$ competition graph for some positive
integers $i$ and $j$. Then $\omega(G)\leq ij-j+1$. Further, the upper bound is
sharp if and only if there is a $(j(ij-j+1)/i,ij-j+1,j,i,1)$-BIBD.

###### Proof.

By Corollary 2.3(c), it directly follows that $\omega(G)\leq j(i-1)+1$.

There exists an $\langle i,j\rangle$ digraph $D$ whose competition graph is
$G$. To show the “only if” part of the “further” part, suppose that $G$ has a
clique $K$ of size $ij-j+1$. For any $u\in K$,

$\displaystyle ij-j=d_{G[K]}(u)=\left|\bigcup_{v\in
N^{+}_{D}(u)}(N^{-}_{D}(v)-\\{u\\})\cap K\right|\leq\sum_{v\in
N^{+}_{D}(u)}|(N^{-}_{D}(v)-\\{u\\})\cap K|$ $\displaystyle\leq\sum_{v\in
N^{+}_{D}(u)}|(N^{-}_{D}(v)-\\{u\\})|\leq\sum_{v\in
N^{+}_{D}(u)}(i-1)\leq(i-1)j$

where $G[K]$ denotes the subgraph of $G$ induced by $K$. Thus the inequalities
above become equalities. The first inequality being equality implies that for
any distinct $u$ and $v$ in $K$,

$\left|N_{D}^{+}(u)\cap N_{D}^{+}(v)\right|=1.$ (1)

It follows from the conversions of the second and the third inequalities that
for any vertex $v\in\bigcup_{u\in K}N^{+}_{D}(u)$,

$N^{-}_{D}(v)\subseteq K\quad\text{ and }\quad d_{D}^{-}(v)=i,$ (2)

respectively. By the conversion of the last inequality, it is immediately true
that for each vertex $u$ in $K$,

$d_{D}^{+}(u)=j.$ (3)

Set

$L=\\{N^{-}_{D}(v)\colon\,v\in N^{+}_{D}(u)\text{ for some }u\in K\\}.$

We regard the vertices in $K$ (resp. the elements in $L$) as the varieties
(resp. the blocks). Then, by (1), (2), and (3), we have a
$(|L|,ij-j+1,j,i,1)$-BIBD. It is well-known that for a
$(b,v,r,k,\lambda)$-BIBD, $bk=vr$. Therefore $|L|=j(ij-j+1)/i$. Thus there is
a $(j(ij-j+1)/i,ij-j+1,j,i,1)$-BIBD.

To show the “if” part, suppose that there is a
$(j(ij-j+1)/i,ij-j+1,j,i,1)$-BIBD. Let $\\{x_{1},x_{2},\ldots,x_{ij-j+1}\\}$
be the set of varieties and $B_{1},\ldots,B_{j(ij-j+1)/i}$ be the blocks of
the design. Now we define a digraph $D$ such that the vertex set is

$\\{u_{1},u_{2},\ldots,u_{ij-j+1}\\}\cup\\{v_{1},v_{2},\ldots,v_{j(ij-j+1)/i}\\}$

and $D$ has an arc $(u_{k},v_{l})$ if and only if $x_{k}\in B_{l}$ for some
integers $1\leq k\leq ij-j+1$ and $1\leq l\leq j(ij-j+1)/i$. Then, since each
variety appears $j$ blocks and each block has $i$ varieties, $D$ is an
$\langle i,j\rangle$ digraph. Moreover, since each pair of varieties is
contained in a unique block, $\\{u_{1},u_{2},\ldots,u_{ij-j+1}\\}$ forms a
clique in the competition graph of $D$. Therefore $\omega(C(D))\geq ij-j+1$.
As we have shown $\omega(C(D))\leq ij-j+1$, $\omega(C(D))=ij-j+1$. ∎

######  Corollary 2.9.

The following are true for any positive integers $i$ and $j$.

  1. (a)

$\omega(G)<ij-j+1$ for an $\langle i,j\rangle$ competition graph $G$ if $i>j$.

  2. (b)

There is a $\langle 2,j\rangle$ competition graph with clique number $j+1$.

  3. (c)

There is a $\langle 3,j\rangle$ competition graph with clique number $2j+1$ if
and only if $j=1$ or $j=3n$ or $j=3n+1$ for some integer $n\geq 1$.

###### Proof.

Let $G$ be an $\langle i,j\rangle$ competition graph with $i>j$. By
Proposition 2.8, $\omega(G)\leq ij-j+1$. To the contrary, suppose
$\omega(G)=ij-j+1$. Then, by the “further” part of Proposition 2.8, there is a
$(j(ij-j+1)/i,ij-j+1,j,i,1)$-BIBD. Now, by Fisher’s inequality, $j\geq i$,
which is a contradiction. Therefore $\omega(G)<ij-j+1$ and the part (a) is
true.

There is a $(j(j+1)/2,j+1,j,2,1)$-BIBD for each positive integer $j$ since the
two-element subsets of a set of $j+1$ elements correspond blocks. Thus, by the
“further” part of Proposition 2.8, the part (b) is true.

It is well-known that a Steiner triple system $S(2,3,n)$ exists if and only if
$n=3$ or $n=6k+1$ or $n=6k+3$ for some integer $k\geq 1$. Thus, by the
“further” part of Proposition 2.8, the part (c) is true. ∎

One may check that for the competition graph $G$ of a digraph $D$, $G$ has a
triangle if and only if $D$ has a subdigraph isomorphic to one of the five
digraphs in Figure 1. Thus we say that a digraph $D$ induces a triangle if $D$
has a subdigraph isomorphic to one of the five digraphs in Figure 1.

(a)

(b)

(c)

(d)

(e)

Figure 1: Triangularize

Hefner et al. introduced the notion of irredundant digraphs. A digraph $D$ is
irredundant if $D$ has no subdigraph isomorphic to $P(2,2)$ (see Figure 2).
Note that any two vertices of an irredundant digraph have at most one common
out-neighbor.

We say that a digraph is an $\langle\bar{i},\bar{j}\rangle$ digraph if it is a
loopless digraph satisfying $d^{-}(x)=0$ or $i$, and $d^{+}(x)=0$ or $j$ for
every vertex $x$. According to this definition, an
$\langle\bar{i},\bar{j}\rangle$ digraph is an $\langle i,j\rangle$ digraph.

Figure 2: $P(2,2)$

######  Proposition 2.10.

Let $G$ be the competition graph of an $\langle i,j\rangle$ digraph $D$ for
some positive integers $i$ and $j$. Then $G$ is chordal if $D$ has no
$\langle\bar{2},\bar{2}\rangle$ subdigraph $D^{\prime}$ satisfying the
following:

  1. (i)

$D^{\prime}$ is irredundant;

  2. (ii)

$D^{\prime}$ does not induce a triangle;

  3. (iii)

$D^{\prime}$ has an arc.

###### Proof.

To show the contrapositive, suppose that $G$ is not chordal. That is, $G$ has
a hole $H:=v_{1}v_{2}\cdots v_{m}v_{1}$ for some integer $m\geq 4$. Then there
are vertices $u_{1},u_{2},\ldots,u_{m}$ in $D$ such that $u_{i}$ is a common
out-neighbor of $v_{i}$ and $v_{i+1}$ for each $1\leq i\leq m$, where we
identify $v_{m+1}$ with $v_{1}$. Now, we consider a subdigraph $D^{\prime}$ of
$D$ with

$V(D^{\prime})=\\{v_{1},v_{2},\ldots,v_{m}\\}\cup\\{u_{1},u_{2},\ldots,u_{m}\\}$

and

$A(D^{\prime})=\\{(v_{i},u_{i}),(v_{i+1},u_{i})\colon\,1\leq i\leq m\\}.$

Clearly, $D^{\prime}$ has an arc and it is irredundant. If $u_{i}=u_{j}$ for
some distinct $i$ and $j$, then $v_{i}$, $v_{i+1}$, $v_{j}$, and $v_{j+1}$, at
least three of which are distinct, form a clique in $G$, which contradicts to
the fact that $H$ is a hole. Thus $u_{1},u_{2},\ldots,u_{m}$ are all distinct.
Therefore $D^{\prime}$ is a $\langle\bar{2},\bar{2}\rangle$ digraph and the
competition graph of $D^{\prime}$ is $H$ with isolated vertices. If
$D^{\prime}$ induces a triangle, then the competition graph of $D^{\prime}$
contains a triangle, which is impossible. Thus $D^{\prime}$ does not induce a
triangle. ∎

Especially, the sufficient condition given in Proposition 2.10 becomes a
necessary and sufficient condition when $j=2$ (Theorem 2.11).

To avoid unnecessary repetition, we call a $\langle\bar{2},\bar{2}\rangle$
digraph satisfying the conditions (i), (ii), and (iii) in Proposition 2.10 a
$\langle\bar{2},\bar{2}\rangle$ good digraph.

######  Theorem 2.11.

Let $G$ be the competition graph of an $\langle i,2\rangle$ digraph $D$ for
some positive integer $i$. Then $G$ is chordal if and only if $D$ has no
$\langle\bar{2},\bar{2}\rangle$ good subdigraph.

###### Proof.

By Proposition 2.10, it suffices to show the “only if” part. To the contrary,
suppose that $G$ is chordal while $D$ has a $\langle\bar{2},\bar{2}\rangle$
good subdigraph $D^{\prime}$. Let $G^{\prime}$ be the competition graph of
$D^{\prime}$. To show that a vertex has degree $0$ or $2$ in $G^{\prime}$,
take a vertex $v$ in $D^{\prime}$. If $d^{+}_{D^{\prime}}(v)=0$, then $v$ is
an isolated vertex in $G^{\prime}$. Suppose $d^{+}_{D^{\prime}}(v)\neq 0$.
Since $D^{\prime}$ is a $\langle\bar{2},\bar{2}\rangle$ digraph,
$d^{+}_{D^{\prime}}(v)=2$ and so there are out-neighbors $x$ and $y$ of $v$.
For the same reason, $x$ (resp. $y$) has an in-neighbor $u$ (resp. $w$) which
is distinct from $v$. Then $u$ and $w$ are neighbors of $v$ in $G$. Since
$D^{\prime}$ is irredundant, $u$ and $w$ are distinct. Thus $v$ has at least
two neighbors in $G^{\prime}$. By Corollary 2.3(c), $v$ has degree $2$ in
$G^{\prime}$. Since $v$ is arbitrarily chosen, we have shown that each vertex
has degree $0$ or $2$ in $G^{\prime}$. Since $D^{\prime}$ has an arc, it has a
vertex of indegree $2$ and so $G^{\prime}$ has an edge. Thus $G^{\prime}$ has
a cycle. Since $D^{\prime}$ does not induce a triangle, no cycle of
$G^{\prime}$ is a triangle. Therefore $G^{\prime}$ has a hole
$H:=v_{1}v_{2}\cdots v_{m}v_{1}$ for some integer $m\geq 4$. Then there are
vertices $u_{1},u_{2},\ldots,u_{m}$ in $D^{\prime}$ such that $u_{i}$ is a
common out-neighbor of $v_{i}$ and $v_{i+1}$ for each $1\leq i\leq m$ where we
identify $v_{m+1}$ with $v_{1}$. Since $D^{\prime}$ is a
$\langle\bar{2},\bar{2}\rangle$ digraph, $u_{1},u_{2},\ldots,u_{m}$ are all
distinct. Thus, for each $1\leq i\leq m$,

$N^{+}_{D^{\prime}}(v_{i})=\\{u_{i-1},u_{i}\\}$

where we identify $u_{0}$ with $u_{m}$. Then, since $D$ is an $\langle
i,2\rangle$ digraph,

$N^{+}_{D}(v_{i})=N^{+}_{D^{\prime}}(v_{i})=\\{u_{i-1},u_{i}\\}$

for each $1\leq i\leq m$. We note that
$\\{u_{i-1},u_{i}\\}\cap\\{u_{j-1},u_{j}\\}=\emptyset$ if $|i-j|\geq 2$.
Therefore, for any nonconsecutive $v_{i}$ and $v_{j}$ in $H$, they have no
common out-neighbor in $D$ and so they are not adjacent in $G$. Hence, $H$ is
a hole of $G$, which is a contradiction that $G$ is chordal. ∎

######  Corollary 2.12.

Let $G$ be the competition graph of a $\langle 2,2\rangle$ digraph $D$. Then
$G$ is interval if and only if there is no $\langle\bar{2},\bar{2}\rangle$
good subdigraph of $D$.

###### Proof.

By Corollary 2.3(c), each vertex of $G$ has degree at most $2$. Thus $G$ is
the union of paths and cycles. Therefore $G$ is interval if and only if it is
chordal, and so the statement is immediately true by Theorem 2.11. ∎

##  3 The set containment relation on $\\{\mathcal{G}_{\langle
i,j\rangle}\colon\,i,j\geq 1\\}$

We recall that $\mathcal{G}_{\langle i,j\rangle}$ denotes the family of
$\langle i,j\rangle$ competition graphs. In this section, we take a look at
set containment between $\mathcal{G}_{\langle i,j\rangle}$ and
$\mathcal{G}_{\langle k,l\rangle}$ for given positive integers $i$, $j$, $k$,
and $l$ with $(i,j)\neq(k,l)$. By symmetry, it is sufficient to consider the
following four cases.

(1) $i=k$, $j>l$; (2) $i>k$, $j>l$; (3) $i>k$, $j=l$; (4) $i>k$, $j<l$.

This section will focus on proving the following theorem.

######  Theorem 3.1.

Let $i$, $j$, $k$, and $l$ be positive integers satisfying $(i,j)\neq(k,l)$.
Without loss of generality, assume $i\geq k$. Then there are four cases and
the following hold.

  1. (1)

If $i=k$ and $j>l$, then

$\begin{cases}\mathcal{G}_{\langle i,j\rangle}=\mathcal{G}_{\langle
k,l\rangle}&\text{if }i=k=1;\\\ \mathcal{G}_{\langle
k,l\rangle}\subsetneq\mathcal{G}_{\langle i,j\rangle}&\text{if
}i=k>1.\end{cases}$

  2. (2)

If $i>k$ and $j>l$, then $\mathcal{G}_{\langle
k,l\rangle}\subsetneq\mathcal{G}_{\langle i,j\rangle}$.

  3. (3)

If $i>k$ and $j=l$, then $\mathcal{G}_{\langle
k,l\rangle}\subsetneq\mathcal{G}_{\langle i,j\rangle}$.

  4. (4)

If $i>k$ and $j<l$, then the following are true.

    1. (a)

$\begin{cases}\mathcal{G}_{\langle k,l\rangle}\subsetneq\mathcal{G}_{\langle
i,j\rangle}&\text{if }k=1;\\\ \mathcal{G}_{\langle
k,l\rangle}\not\subseteq\mathcal{G}_{\langle i,j\rangle}&\text{if
}k>1.\end{cases}$

    2. (b)

$\mathcal{G}_{\langle i,j\rangle}\not\subseteq\mathcal{G}_{\langle
k,l\rangle}$ if $i>k^{2}-k+1$ or $(i-1)j>(k-1)l$ or $j\geq k\geq 2$.

In order to establish the proof, we undertake the following necessary
preparations.

######  Proposition 3.2.

A graph $G$ is a $\langle 1,j\rangle$ competition graph for some positive
integer $j$ if and only if $G$ is edgeless, that is, $E(G)=\emptyset$.

###### Proof.

An edgeless graph is an $\langle i,j\rangle$ digraph for any positive integers
$i$ and $j$ and is the competition graph of itself. Thus the “if” part is
clear. The “only if” part directly follows Corollary 2.3(a). ∎

######  Proposition 3.3.

A graph $G$ is an $\langle i,1\rangle$ competition graph for some positive
integer $i$ if and only if $G$ is trivial or is the disjoint union of at least
two complete graphs each of which has size at most $i$.

###### Proof.

To show the “only if” part, suppose that $G$ is an $\langle i,1\rangle$
competition graph for some positive integer $i$. By Theorem 2.7(iii), there is
an edge clique cover $\mathcal{C}$ in $\mathbf{C}(G,i,1)$. Then each vertex of
$G$ belongs to at most one clique in $\mathcal{C}$ and so $G$ is the disjoint
union of cliques each of which has size at most $i$. Moreover, by Theorem
2.7(ii), $G$ is not a nontrivial complete graph. Thus $G$ is trivial or is the
disjoint union of at least two complete graphs each of which has size at most
$i$.

To show the “if” part, suppose that $G$ is trivial or is the disjoint union of
at least two complete graphs each of which has size at most $i$ for some
positive integer $i$. Then $G$ is not a nontrivial complete graph and the
collection of components of $G$ is an edge clique cover in
$\mathbf{C}(G,i,1)$. Thus $G$ is an $\langle i,1\rangle$ competition graph by
Theorem 2.7. ∎

######  Proposition 3.4.

Let $i$, $j$, $k$, $l$, $m$, and $n$ be positive integers satisfying $i,j\geq
2$, $j>l$, and $(i-1)j>(m-1)n$. Then $\mathcal{G}_{\langle
i,j\rangle}\not\subseteq\mathcal{G}_{\langle
k,l\rangle}\cup\mathcal{G}_{\langle m,n\rangle}$.

###### Proof.

Consider a star $K_{1,j}$ with the center $u$ and the leaves
$u_{1},\ldots,u_{j}$. We replace each edge $uu_{t}$ of $K_{1,j}$ with the
complete graph $C_{t}$ having $\\{u,u^{1}_{t},\ldots,u^{i-1}_{t}\\}$ as the
vertex set for each $1\leq t\leq j$ to obtain a graph $G^{*}_{i,j}$ (see
Figure 3 for $G^{*}_{5,3}$). Then
$\\{C_{1},\ldots,C_{j}\\}\in\mathbf{C}(G^{*}_{i,j},i,j)$. Since $i,j\geq 2$,
$G^{*}_{i,j}\not\cong K_{2}$. Thus $G^{*}_{i,j}\in\mathcal{G}_{\langle
i,j\rangle}$ by Theorem 2.7. We note that the subgraph of $G^{*}_{i,j}$
induced by $\\{u,u_{1}^{1},\ldots,u_{j}^{1}\\}$ is isomorphic to $K_{1,j}$.
Then, since $j>l$, $G^{*}_{i,j}$ has a subgraph isomorphic to $K_{1,l+1}$ and
so, by Corollary 2.3(b), $G^{*}_{i,j}\not\in\mathcal{G}_{\langle k,l\rangle}$.
Since $u$ has degree $(i-1)j$ in $G^{*}_{i,j}$ and $(i-1)j>(m-1)n$,
$G^{*}_{i,j}\not\in\mathcal{G}_{\langle m,n\rangle}$ by Corollary 2.3(c).
Therefore $G^{*}_{i,j}\in\mathcal{G}_{\langle
i,j\rangle}-(\mathcal{G}_{\langle k,l\rangle}\cup\mathcal{G}_{\langle
m,n\rangle})$ and so $\mathcal{G}_{\langle
i,j\rangle}\not\subseteq\mathcal{G}_{\langle
k,l\rangle}\cup\mathcal{G}_{\langle m,n\rangle}$. ∎

$u$$u_{1}^{1}$$u_{1}^{2}$$u_{1}^{3}$$u_{1}^{4}$$u_{2}^{1}$$u_{2}^{2}$$u_{2}^{3}$$u_{2}^{4}$$u_{3}^{1}$$u_{3}^{2}$$u_{3}^{3}$$u_{3}^{4}$

Figure 3: $G^{*}_{5,3}$

######  Proposition 3.5.

Let $i$, $j$, $k$, and $l$ be positive integers satisfying $i>k^{2}-k+1$. Then
$\mathcal{G}_{\langle i,j\rangle}\not\subseteq\mathcal{G}_{\langle
k,l\rangle}$.

###### Proof.

By Proposition 3.3, $K_{i}\cup K_{i}\in\mathcal{G}_{\langle
i,1\rangle}\subseteq\mathcal{G}_{\langle i,j\rangle}$. If $K_{i}\cup
K_{i}\in\mathcal{G}_{\langle k,l\rangle}$, then, by Corollary 2.3(a),

$(i-1)i=|E(K_{i}\cup K_{i})|\leq\frac{k(k-1)}{2}|V(K_{i}\cup
K_{i})|=(k^{2}-k)i$

and so $i\leq k^{2}-k+1$. Since $i>k^{2}-k+1$, $K_{i}\cup
K_{i}\not\in\mathcal{G}_{\langle k,l\rangle}$. Thus $K_{i}\cup
K_{i}\in\mathcal{G}_{\langle i,j\rangle}-\mathcal{G}_{\langle k,l\rangle}$. ∎

######  Proposition 3.6.

Let $i$, $j$, $k$, and $l$ be positive integers satisfying $j\geq k\geq 2$ and
$i>k$. Then $\mathcal{G}_{\langle i,j\rangle}\not\subseteq\mathcal{G}_{\langle
k,l\rangle}$.

###### Proof.

It suffices to construct a $\langle k+1,k\rangle$ competition graph $G$
satisfying

$\frac{|E(G)|}{|V(G)|}>\frac{k(k-1)}{2}.$

For, $G\in\mathcal{G}_{\langle k+1,k\rangle}\subseteq\mathcal{G}_{\langle
i,j\rangle}$ while $G\notin\mathcal{G}_{\langle k,l\rangle}$ by Corollary
2.3(a).

Given positive integers $m$ and $n$, we consider the Cartesian product of $n$
copies of $[m]=\\{1,\ldots,m\\}$, i.e.

$[m]^{n}:=\\{(x_{1},\ldots,x_{n})\in\mathbb{Z}^{n}\colon\,1\leq
x_{1},\ldots,x_{n}\leq m\\}.$

Now we consider the graph $G$ such that $V(G)=[k+1]^{k}$ and two vertices are
adjacent if and only if they differ in exactly one component. Then
$|V(G)|=(k+1)^{k}$. Moreover, each vertex is adjacent with exactly other
$k^{2}$ vertices and so

$|E(G)|=\frac{1}{2}\sum_{v\in V(G)}d(v)=\frac{k^{2}|V(G)|}{2}.$

Thus $G$ satisfies

$\frac{|E(G)|}{|V(G)|}>\frac{k(k-1)}{2}.$

It remains to show $G\in\mathcal{G}_{\langle k+1,k\rangle}$. Given an integer
$t\in[k]$ and a vertex $u$ of $G$, let

$C_{t}^{u}=\\{(x_{1},\ldots,x_{k})\in V(G)\colon\,x_{i}=u_{i}\text{ for each
}i\in[k]-\\{t\\}\\}.$

Then each $C_{t}^{u}$ forms a clique of size $k+1$ in $G$. If $u$ and $v$ are
adjacent in $G$, then they differ in exactly one component, say the $p$th
component, and so they are contained in $C_{p}^{u}$. Thus
$\mathcal{C}:=\\{C_{t}^{u}\colon\,1\leq t\leq k,u\in[k+1]^{k}\\}$ is an edge
clique cover of $G$. For each vertex $u$ of $G$, there are exactly $k$ cliques
$C_{1}^{u},\ldots,C_{k}^{u}$ in $\mathcal{C}$ containing $u$. Thus

$(k+1)|\mathcal{C}|=\sum_{C\in\mathcal{C}}\sum_{u\in
C}1=|\\{(C,u)\colon\,C\in\mathcal{C},u\in C\\}|=\sum_{u\in V(G)}\sum_{u\in
C\in\mathcal{C}}1=k|V(G)|$

and so $|\mathcal{C}|\leq|V(G)|$. Therefore

$\mathcal{C}\in\mathbf{C}(G,k+1,k)$

and so, by Theorem 2.7, $G$ is a $\langle k+1,k\rangle$ competition graph. ∎

Now we are ready to prove Theorem 3.1.

###### Proof of Theorem 3.1.

To show (1), suppose that $i=k$ and $j>l$. Then $\mathcal{G}_{\langle
k,l\rangle}\subseteq\mathcal{G}_{\langle i,j\rangle}$ and $j\geq 2$. If
$i=k=1$, then $\mathcal{G}_{\langle i,j\rangle}=\mathcal{G}_{\langle
k,l\rangle}$ by Proposition 3.2. If $i=k>1$, then $\mathcal{G}_{\langle
i,j\rangle}\not\subseteq\mathcal{G}_{\langle k,l\rangle}$ by Proposition 3.4
and so $\mathcal{G}_{\langle k,l\rangle}\subsetneq\mathcal{G}_{\langle
i,j\rangle}$. Thus (1) holds.

Suppose that $i>k$ and $j>l$. Then $\mathcal{G}_{\langle
k,l\rangle}\subseteq\mathcal{G}_{\langle i,j\rangle}$ and $i,j\geq 2$.
Moreover, $\mathcal{G}_{\langle k,l\rangle}\subsetneq\mathcal{G}_{\langle
i,j\rangle}$ by Proposition 3.4. Thus (2) holds.

Suppose that $i>k$ and $j=l$. Then $\mathcal{G}_{\langle
k,l\rangle}\subseteq\mathcal{G}_{\langle i,j\rangle}$ and $i\geq 2$. If
$j=l=1$, then the disjoint union of two complete graphs each of whose order is
$i$ is an $\langle i,j\rangle$ competition graph which is not a $\langle
k,l\rangle$ competition graph by Proposition 3.3 and so $\mathcal{G}_{\langle
k,l\rangle}\subsetneq\mathcal{G}_{\langle i,j\rangle}$. If $j=l\geq 2$, then
Proposition 3.4 implies $\mathcal{G}_{\langle
i,j\rangle}\not\subseteq\mathcal{G}_{\langle k,l\rangle}$ by substituting
$(i,j,k,l)$ for $(i,j,m,n)$. Thus $\mathcal{G}_{\langle
k,l\rangle}\subsetneq\mathcal{G}_{\langle i,j\rangle}$. Therefore (3) holds.

Finally, to show (4), suppose that $i>k$ and $j<l$. Then $i\geq 2$ and so it
is easy to check that $K_{2}\cup K_{1}\in\mathcal{G}_{\langle i,j\rangle}$ by
Theorem 2.7. Thus, if $k=1$, $\mathcal{G}_{\langle
k,l\rangle}\subsetneq\mathcal{G}_{\langle i,j\rangle}$ by Propositions 3.2. If
$k\geq 2$, then Proposition 3.4 implies $\mathcal{G}_{\langle
k,l\rangle}\not\subseteq\mathcal{G}_{\langle i,j\rangle}$ by substituting
$(k,l,i,j)$ for $(i,j,k,l)$. Thus (a) is true. Now we prove (b). If
$i>k^{2}-k+1$, then $\mathcal{G}_{\langle
i,j\rangle}\not\subseteq\mathcal{G}_{\langle k,l\rangle}$ by Proposition 3.5.
Suppose $(i-1)j>(k-1)l$. If $k=1$, then we have already checked that
$\mathcal{G}_{\langle k,l\rangle}\subsetneq\mathcal{G}_{\langle i,j\rangle}$
and so $\mathcal{G}_{\langle i,j\rangle}\not\subseteq\mathcal{G}_{\langle
k,l\rangle}$. If $k\geq 2$, then $\mathcal{G}_{\langle
i,j\rangle}\not\subseteq\mathcal{G}_{\langle k,l\rangle}$ by Proposition 3.4.
If $j\geq k\geq 2$, then $\mathcal{G}_{\langle
i,j\rangle}\not\subseteq\mathcal{G}_{\langle k,l\rangle}$ by Proposition 3.6.
Hence we have shown that (4) holds. ∎

##  4 Concluding remarks

To fully address the case (4) of Theorem 3.1, we need to find out whether or
not there is a graph belonging to $\mathcal{G}_{\langle
i,j\rangle}-\mathcal{G}_{\langle k,l\rangle}$ when $k^{2}-k+1\geq i>k\geq 2$,
$j<\min(k,l)$, and $(i-1)j\leq(k-1)l$. This problem seems challenging to
resolve due to the following reasons. Consider $(i,j,k,l)=(3,1,2,t)$ and
$(i,j,k,l)=(4,1,3,t)$ for each integer $t\geq 2$, and $(i,j,k,l)=(5,1,3,2)$
all of which satisfy the conditions given above. Yet, one may check that
$\mathcal{G}_{\langle 3,1\rangle}\subsetneq\mathcal{G}_{\langle 2,l\rangle}$
and $\mathcal{G}_{\langle 4,1\rangle}\subsetneq\mathcal{G}_{\langle
3,l\rangle}$ for all $l\geq 2$ by Proposition 3.3 and Theorem 2.7, while
$\mathcal{G}_{\langle 5,1\rangle}\not\subseteq\mathcal{G}_{\langle
3,2\rangle}$ since $K_{5}\cup K_{5}\in\mathcal{G}_{\langle
5,1\rangle}-\mathcal{G}_{\langle 3,2\rangle}$.

##  5 Acknowledgement

This work was supported by Science Research Center Program through the
National Research Foundation of Korea(NRF) Grant funded by the Korean
Government (MSIP)(NRF-2022R1A2C
1009648 and 2016R1A5A1008055). Especially, the first author was supported by
Basic Science Research Program through the National Research Foundation of
Korea(NRF) funded by the Ministry of Education (NRF-2022R1A6A3A13063000).

## References

  * [1] A Bondy and USR Murty.  Graph Theory. LNCS, volume 655.  Springer, 2010.
  * [2] Joel E Cohen.  Interval graphs and food webs: a finding and a problem.  RAND Corporation Document, 17696, 1968.
  * [3] Suh-Ryung Kim.  The competition number and its variants.  Annals of Discrete Mathematics, volume 55, pages 313–326. Elsevier, 1993.
  * [4] J Richard Lundgren.  Food webs, competition graphs, competition-common enemy graphs, and niche graphs.  Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, pages 221–243. Springer, 1989.
  * [5] Arundhati Raychaudhuri and Fred S Roberts.  Generalized competition graphs and their applications.  Methods of Operations Research, 49:295–311, 1985.
  * [6] Han Hyuk Cho, Suh-Ryung Kim, and Yunsun Nam.  The m-step competition graph of a digraph.  Discrete Applied Mathematics, 105(1-3):115–127, 2000.
  * [7] Myungho Choi and Suh-Ryung Kim.  Digraphs whose m-step competition graphs are trees.  Discrete Applied Mathematics, 338:234–246, 2023.
  * [8] Seung Chul Lee, Jihoon Choi, Suh-Ryung Kim, and Yoshio Sano.  On the phylogeny graphs of degree-bounded digraphs.  Discrete Applied Mathematics, 233:83–93, 2017.
  * [9] Soogang Eoh and Suh-Ryung Kim.  On chordal phylogeny graphs.  Discrete Applied Mathematics, 302:80–91, 2021.
  * [10] Robert J Opsut.  On the computation of the competition number of a graph.  SIAM Journal on Algebraic Discrete Methods, 3(4):410–428, 1982\.
  * [11] Ronald D Dutton and Robert C Brigham.  A characterization of competition graphs.  Discrete Applied Mathematics, 6:315–317, 1983.
  * [12] Fred S Roberts and Jeffrey E Steif.  A characterization of competition graphs of arbitrary digraphs.  Discrete Applied Mathematics, 6(3):323–326, 1983.
  * [13] J Richard Lundgren and John S Maybee.  A characterization of graphs of competition number $m$.  Discrete Applied Mathematics, 6(3):319–322, 1983.
  * [14] Kim AS Hefner, Kathryn F Jones, Suh-ryung Kim, J Richard Lundgren, and Fred S Roberts.  $(i,j)$ competition graphs.  Discrete applied mathematics, 32(3):214–262, 1991.
  * [15] P. Hall.  On representatives of subsets.  Journal of The London Mathematical Society, 10(1):26–30, 1935.