Competition Numbers of Several Kinds of Triangulations of a Sphere

Yongqiang Zhao¹, Zhiming Fang^2,3, Yonggang Cui¹, Guoyan Ye¹, Zhijun Cao¹

¹School of Science, Shijiazhuang University, Shijiazhuang, China.
²Zhejiang Jinyun High School, Lishui, China.
³School of Science, Hebei University of Technology, Tianjin, China.

DOI: 10.4236/ojdm.2017.72006                

Abstract

It is hard to compute the competition number for a graph in general and characterizing a graph by its competition number has been one of important research problems in the study of competition graphs. Sano pointed out that it would be interesting to compute the competition numbers of some triangulations of a sphere as he got the exact value of the competition numbers of regular polyhedra. In this paper, we study the competition numbers of several kinds of triangulations of a sphere, and get the exact values of the competition numbers of a 24-hedron obtained from a hexahedron by adding a vertex in each face of the hexahedron and joining the vertex added in a face with the four vertices of the face, a class of dodecahedra constructed from a hexahedron by adding a diagonal in each face of the hexahedron, and a triangulation of a sphere with 3n (n≥2) vertices.

Keywords

Competition Graph, Competition Number, Edge Clique Cover, Vertex Clique Cover, Triangulation of a Sphere

1. Introduction and Preliminary

Let $G=\left(V,E\right)$ be a graph in which $V$ is the vertex set and $E$ the edge set. We always use $\left|V\right|$ and $\left|E\right|$ to denote the vertex number and the edge number of $G$ , respectively. The notion of competition graph was introduced by Cohen [1] in connection with a problem in ecology. Let $D=\left(V,A\right)$ be a digraph in which $V$ is the vertex set and $A$ the set of directed arcs. The competition graph $C\left(D\right)$ of $D$ is the undirected graph $G$ with the same vertex set as $D$ and with an edge $uv\in E\left(G\right)$ if and only if there exists some vertex $x\in V\left(D\right)$ such that $\left(u,x\right),\left(v,x\right)\in A\left(D\right)$ . We say that a graph $G$ is a com- petition graph if there exists a digraph $D$ such that $C\left(D\right)=G$ .

Roberts [2] observed that every graph together with sufficiently many isolated vertices is the competition graph of an acyclic digraph. The competition number $k\left(G\right)$ of a graph $G$ is defined to be the smallest number $k$ such that $G$ together with $k$ isolated vertices added is the competition graph of an acyclic digraph. It is difficult to compute the competition number of a graph in general as Opsut [3] has shown that the computation of the competition number of a graph is an NP-hard problem. But it has been one of important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, many papers related to graphs’ competition numbers have appeared. Kim, et al., [4] studied the competition numbers of connected graphs with exactly one or two triangles. Sano [5] studied the competition numbers of regular polyhedra. Kim, et al., [6] studied the competition numbers of Johnson graphs. Park and Sano [7] [8] studied the competition numbers of some kind of Hamming graphs. Kim, et al., [9] studied the competition numbers of the complement of a cycle. Furthermore, there are some papers (see [10] [11] [12] [13] [14] ) focused on the competition numbers of the complete multipartite graphs, and some papers (see [15] - [23] ) concentrated on the relationship between the competition number and the number of holes of a graph. A cycle of length at least 4 of a graph as an induced subgraph is called a hole of the graph. We use $I_r$ to denote the graph consisting only of $r$ isolated vertices, and $G\cup I_r$ the disjoint union of $G$ and $I_r$ . The induced subgraph $G\left[S\right]$ of $G$ is a subgraph of $G$ whose vertex set is $S$ and whose edge set is the set of those edges of $G$ that have both ends in $S$ .

All graphs considered in this paper are simple and connected. For a vertex $v$ in a graph $G$ , let the open neighborhood of $v$ be defined by

$N_G\left(v\right)=\left\{u|u\text{isadjacentto}v\right\}$ . For any set $U$ of vertices in $G$ , we define the neighborhood of $U$ in $G$ to be the set of all vertices adjacent to vertices in $U$ , this set is denoted by $N_G\left(U\right)$ . Let $N_G\left[U\right]=N_G\left(U\right)\cup U$ and

$E_G\left[U\right]=\left\{e\in E\left(G\right)|e\text{hasanendpointin}U\right\}$ . We denote by the same symbol $N_G\left[U\right]$ the subgraph of $G$ induced by $N_G\left[U\right]$ . Note that $E_G\left[U\right]$ is con- tained in the edge set of the subgraph $N_G\left[U\right]$ .

A subset $U$ of the vertex set of a graph $G$ is called a clique of $G$ if $G\left[U\right]$ is a complete graph. For a clique $U$ of a graph $G$ and an edge $e$ of $G$ , we say $e$ is covered by $U$ if both of the endpoints of $e$ are contained in $U$ . An edge clique cover of a graph $G$ is a family of cliques such that each edge of $G$ is covered by some clique in the family. The edge clique cover number ${\theta }_e\left(G\right)$ of a graph $G$ is the minimum size of an edge clique cover of $G$ . A vertex clique cover of a graph $G$ is a family of cliques such that each vertex of $G$ is contained in some clique in the family. The vertex clique cover number ${\theta }_v\left(G\right)$ of a graph $G$ is the minimum size of a vertex clique cover of $G$ .

Let $G$ be a graph and $F\subseteq E\left(G\right)$ be a subset of the edge set of $G$ . An edge clique cover of $F$ in $G$ is a family of cliques of $G$ such that each edge in $F$ is covered by some clique in the family. The edge clique cover number ${\theta }_e\left(F;G\right)$ of $F\subseteq E\left(G\right)$ in $G$ is defined as the minimum size of an edge clique cover of $F$ in $G$ , i.e.,

${\theta }_e\left(F;G\right)=\min \left\{\left|U\right||U\text{isanedgecliquecoverof}F\text{in}G\right\}.$ Note that the edge clique cover number ${\theta }_e\left(E\left(G\right);G\right)$ of $E\left(G\right)$ in a graph $G$ is equal to the edge clique cover number ${\theta }_e\left(G\right)$ of the graph $G$ .

Opsut [3] gave the following two lower bounds for the competition number of a graph.

Theorem 1 (Opsut [3] ). For any graph $G$ , $k\left(G\right)\ge {\theta }_e\left(G\right)-\left|V\left(G\right)\right|+2$ .

Theorem 2 (Opsut [3] ). For any graph $G$ , $k\left(G\right)\ge \min \left\{{\theta }_v\left(N_G\left(v\right)\right)|v\in V\left(G\right)\right\}$ .

Recently, Sano [24] gave a generalization of the above two lower bounds as follows:

Theorem 3 (Sano [24] ). Let $G=\left(V,E\right)$ be a graph. Let $m$ be an integer such that $1\le m\le \left|V\right|$ . Then

$k\left(G\right)\ge \underset{U\in \left(\begin{array}{c}V\\ m\end{array}\right)}{\min }{\theta }_e\left(E_G\left[U\right];N_G\left[U\right]\right)-m+1,$

where $\left(\begin{array}{c}V\\ m\end{array}\right)$ denotes the set of all $m$ -subsets of $V$ .

The following results from [25] will be used in this paper.

Theorem 4 (Harary et al. [25] ). Let $D=\left(V,A\right)$ be a digraph. Then $D$ is acyclic if and only if there exists an ordering of vertices, $\sigma =\left[v_1,v_2,\cdots ,v_n\right]$ , such that one of the following two conditions holds:

1) For all $i,j\in \left\{1,2,\cdots ,n\right\}$ , $\left(v_i,v_j\right)\in A$ implies that $i<j$ ;

2) For all $i,j\in \left\{1,2,\cdots ,n\right\}$ , $\left(v_i,v_j\right)\in A$ implies that $i>j$ .

Sano [5] pointed out that it would be interesting to compute the competition numbers of some triangulations of a sphere as he obtained the exact value of the competition numbers of regular polyhedra. In this paper we try to study the competition numbers of several kinds of triangulations of a sphere. In Section 2, we study the competition number of a 24-hedron constructed from a hexahedron by adding a vertex in each face of the hexahedron and joining the vertex added in a face with the four vertices of the face. In Section 3, we study the competition numbers of a class of dodecahedra obtained from a hexahedron by adding a diagonal in each face of the hexahedron. In Section 4, we study the competition number of a triangulation of a sphere with $3n\left(n\ge 2\right)$ vertices.

In the following, “ $S\to v$ ” means that we make an arc from each vertex in $S$ to the vertex $v$ .

2. A 24-Hedron

In this section we study the competition number of a 24-hedron obtained from a hexahedron by adding a vertex in each face of the hexahedron and joining the vertex added in a face with the four vertices of the face. See Figure 1.

Theorem 5. Let $\mathbb{T}$ be the 24-hedron shown in Figure 1(b). Then $k\left(\mathbb{T}\right)=3$ .

Proof. Let $V\left(\mathbb{T}\right)=\left\{v_1,v_2,\cdots ,v_{14}\right\}$ and suppose that the adjacencies between two vertices are given as Figure 2. Let

Figure 1. Planar embeddings of a hexahedron and a 24-hedron.

Figure 2. An edge clique cover of the 24-hedron $\mathbb{T}$ .

$\begin{array}{l}{S}_1=\left\{v_2,v_7,v_9\right\},S_2=\left\{v_1,v_2,v_{13}\right\},S_3=\left\{v_1,v_4,v_{14}\right\},S_4=\left\{v_2,v_3,v_4\right\},\\ S_5=\left\{v_3,v_6,v_7\right\},S_6=\left\{v_4,v_5,v_6\right\},S_7=\left\{v_5,v_{10},v_{14}\right\},S_8=\left\{v_6,v_8,v_{10}\right\},\\ S_9=\left\{v_7,v_8,v_{11}\right\},S_{10}=\left\{v_9,v_{11},v_{13}\right\},S_{11}=\left\{v_{10},v_{11},v_{12}\right\},S_{12}=\left\{v_{12},v_{13},v_{14}\right\}.\end{array}$

Then the family $\left\{S_1,S_2,\cdots ,S_{12}\right\}$ is an edge clique cover of $\mathbb{T}$ .

Now, we define a digraph $D$ as follows. Let

$V\left(D\right)=V\left(\mathbb{T}\right)\cup \left\{a,b,c\right\},$

$\begin{array}{l}{S}_1\to a,S_2\to b,S_3\to c,S_4\to v_1,S_5\to v_2,S_6\to v_3,\\ S_7\to v_4,S_8\to v_5,S_9\to v_6,S_{10}\to v_7,S_{11}\to v_8,S_{12}\to v_9,\end{array}$

where $a,b$ and $c$ are new added vertices. Then by Theorem 4 the digraph $D$ is acyclic and $C\left(D\right)=\mathbb{T}\cup \left\{a,b,c\right\}$ . Hence we have

$k\left(\mathbb{T}\right)\le 3.$ (1)

On the other hand, by Theorem 3 with $m=2$ , we have

$k\left(\mathbb{T}\right)\ge \underset{U\in \left(\begin{array}{c}V\\ 2\end{array}\right)}{\min }{\theta }_e\left(E_{\mathbb{T}}\left[U\right];N_{\mathbb{T}}\left[U\right]\right)-1.$

There are 7 different cases for the set $E_{\mathbb{T}}\left[U\right]$ of edges in the subgraph

$N_{\mathbb{T}}\left[U\right]$ , where $U\in \left(\begin{array}{c}V\\ 2\end{array}\right)$ (see Figure 3):

1) If $\mathbb{T}\left[U\right]=P_2$ , then ${\theta }_e\left(E_{\mathbb{T}}\left[U\right];N_{\mathbb{T}}\left[U\right]\right)=5;$

2) If $\mathbb{T}\left[U\right]=I_2$ , then ${\theta }_e\left(E_{\mathbb{T}}\left[U\right];N_{\mathbb{T}}\left[U\right]\right)=6;$

3) If $\mathbb{T}\left[U\right]=I_2$ , then ${\theta }_e\left(E_{\mathbb{T}}\left[U\right];N_{\mathbb{T}}\left[U\right]\right)=6;$

4) If $\mathbb{T}\left[U\right]=I_2$ , then ${\theta }_e\left(E_{\mathbb{T}}\left[U\right];N_{\mathbb{T}}\left[U\right]\right)=4;$

5) If $\mathbb{T}\left[U\right]=I_2$ , then ${\theta }_e\left(E_{\mathbb{T}}\left[U\right];N_{\mathbb{T}}\left[U\right]\right)=4;$

6) If $\mathbb{T}\left[U\right]=P_2$ , then ${\theta }_e\left(E_{\mathbb{T}}\left[U\right];N_{\mathbb{T}}\left[U\right]\right)=4;$

7) If $\mathbb{T}\left[U\right]=I_2$ , then ${\theta }_e\left(E_{\mathbb{T}}\left[U\right];N_{\mathbb{T}}\left[U\right]\right)=5.$

Thus it holds that

$\underset{U\in \left(\begin{array}{c}V\\ 2\end{array}\right)}{\min }{\theta }_e\left(E_{\mathbb{T}}\left[U\right];N_{\mathbb{T}}\left[U\right]\right)=4.$

Hence we have

$k\left(\mathbb{T}\right)\ge 3.$ (2)

Combining inequalities (1) and (2) we have $k\left(\mathbb{T}\right)=3$ .

3. A Class of Dodecahedra

In this section we study the competition numbers of a class of dodecahedra constructed from a hexahedron by adding a diagonal in each face of the hexahedron. It is not difficult to see that there are 6 nonisomorphic such dodecahedra. Denote the 6 different dodecahedra by ${ℍ}_1$ , ${ℍ}_2$ , ${ℍ}_3$ , ${ℍ}_4$ , ${ℍ}_5$ and ${ℍ}_6$ , respectively. See Figure 4.

Figure 3. The set $E_{\mathbb{T}}\left[U\right]$ of edges in the subgraph $N_{\mathbb{T}}\left[U\right]$ .

Figure 4. 6 nonisomorphic dodecahedra obtained from a hexahedron.

Theorem 6. $k\left({ℍ}_i\right)=\{\begin{array}{ll}2,\hfill & i=1,3;\hfill \\ 1,\hfill & i=2,4,5,6.\hfill \end{array}$

Proof. Let $V\left({ℍ}_i\right)=\left\{v_1,v_2,\cdots ,v_8\right\}$ and suppose that the adjacencies between two vertices are given as Figure 5, where $i=1,2,\cdots ,6$ . Now we define digraphs $D_1,D_2,\cdots ,D_6$ , respectively.

1) $D_1$ .

Let $V\left(D_1\right)=V\left({ℍ}_1\right)\cup \left\{a_1,b_1\right\}$ , and $A\left(D_1\right)$ be defined as follows:

$\begin{array}{l}{S}_1=\left\{v_1,v_2,v_6\right\}\to a_1,S_2=\left\{v_1,v_3,v_5\right\}\to b_1,S_3=\left\{v_2,v_3,v_8\right\}\to v_1,\\ S_4=\left\{v_3,v_4,v_5\right\}\to v_2,S_5=\left\{v_4,v_7,v_8\right\}\to v_3,S_6=\left\{v_5,v_6,v_7\right\}\to v_4,\\ S_7=\left\{v_6,v_8\right\}\to v_5,\end{array}$

where $a_1$ and $b_1$ are new added vertices. Note that the family $\left\{S_1,S_2,\cdots ,S_7\right\}$ is an edge clique cover of ${ℍ}_1$ .

2) $D_2$ .

Let $V\left(D_2\right)=V\left({ℍ}_2\right)\cup \left\{a_2\right\}$ , and $A\left(D_2\right)$ be defined as follows:

$\begin{array}{l}{S}_1=\left\{v_1,v_2,v_3,v_5\right\}\to a_2,S_2=\left\{v_2,v_6,v_8\right\}\to v_1,S_3=\left\{v_3,v_4,v_6\right\}\to v_2,\\ S_4=\left\{v_4,v_5,v_7\right\}\to v_3,S_5=\left\{v_5,v_7,v_8\right\}\to v_4,S_6=\left\{v_6,v_7\right\}\to v_5,\end{array}$

where $a_2$ is a new added vertex. Note that the family $\left\{S_1,S_2,\cdots ,S_6\right\}$ is an edge clique cover of ${ℍ}_2$ .

3) $D_3$ .

Let $V\left(D_3\right)=V\left({ℍ}_3\right)\cup \left\{a_3,b_3\right\}$ , and $A\left(D_3\right)$ be defined as follows:

Figure 5. Edge clique covers for ${ℍ}_1$ , ${ℍ}_2$ , ${ℍ}_3$ , ${ℍ}_4$ , ${ℍ}_5$ and ${ℍ}_6$ .

$\begin{array}{l}{S}_1=\left\{v_1,v_4,v_8\right\}\to a_3,S_2=\left\{v_1,v_2,v_7\right\}\to b_3,S_3=\left\{v_2,v_3,v_4\right\}\to v_1,\\ S_4=\left\{v_3,v_5,v_7\right\}\to v_2,S_5=\left\{v_4,v_5,v_6\right\}\to v_3,S_6=\left\{v_6,v_7,v_8\right\}\to v_4,\end{array}$

where $a_3$ and $b_3$ are new added vertices. Note that the family $\left\{S_1,S_2,\cdots ,S_6\right\}$ is an edge clique cover of ${ℍ}_3$ .

4) $D_4$ .

Let $V\left(D_4\right)=V\left({ℍ}_4\right)\cup \left\{a_4\right\}$ , and $A\left(D_4\right)$ be defined as follows:

$\begin{array}{l}{S}_1=\left\{v_1,v_3,v_4,v_8\right\}\to a_4,S_2=\left\{v_2,v_4,v_6,v_8\right\}\to v_1,S_3=\left\{v_3,v_5,v_7\right\}\to v_2,\\ S_4=\left\{v_4,v_5,v_6\right\}\to v_3,S_5=\left\{v_6,v_7,v_8\right\}\to v_4.\end{array}$

where $a_4$ is a new added vertex. Note that the family $\left\{S_1,S_2,\cdots ,S_5\right\}$ is an edge clique cover of ${ℍ}_4$ .

5) $D_5$ .

Let $V\left(D_5\right)=V\left({ℍ}_5\right)\cup \left\{a_5\right\}$ , and $A\left(D_5\right)$ be defined as follows:

$\begin{array}{l}{S}_1=\left\{v_1,v_3,v_4,v_5\right\}\to a_5,S_2=\left\{v_2,v_6,v_7,v_8\right\}\to v_1,S_3=\left\{v_3,v_6,v_7\right\}\to v_2,\\ S_4=\left\{v_4,v_6,v_8\right\}\to v_3,S_5=\left\{v_5,v_7,v_8\right\}\to v_4,\end{array}$

where $a_5$ is a new added vertex. Note that the family $\left\{S_1,S_2,\cdots ,S_5\right\}$ is an edge clique cover of ${ℍ}_5$ .

6) $D_6$ .

Let $V\left(D_6\right)=V\left({ℍ}_6\right)\cup \left\{a_6\right\}$ , and $A\left(D_6\right)$ be defined as follows:

$\begin{array}{l}{S}_1=\left\{v_1,v_5,v_6,v_7\right\}\to a,S_2=\left\{v_2,v_5,v_7,v_8\right\}\to v_1,S_3=\left\{v_3,v_5,v_6,v_8\right\}\to v_2,\\ S_4=\left\{v_4,v_6,v_7,v_8\right\}\to v_3,\end{array}$

where $a_6$ is a new added vertex. Note that the family $\left\{S_1,S_2,S_3,S_4\right\}$ is an edge clique cover of ${ℍ}_6$ .

By Theorem 4, each $D_i$ is acyclic and

$C\left(D_i\right)=\{\begin{array}{ll}{ℍ}_i\cup \left\{a_i,b_i\right\},\hfill & i=1,3;\hfill \\ {ℍ}_i\cup \left\{a_i\right\},\hfill & i=2,4,5,6.\hfill \end{array}$

Hence we have

$k\left({ℍ}_i\right)\{\begin{array}{ll}\le 2,\hfill & i=1,3;\hfill \\ \le 1,\hfill & i=2,4,5,6.\hfill \end{array}$ (3)

On the other hand, we note that

・ $\delta \left({ℍ}_1\right)=\delta \left({ℍ}_3\right)=4$ and there is no clique with more than 3 vertices in ${ℍ}_1$ and ${ℍ}_3$ , respectively;

・ $N_{{ℍ}_2}\left(v_1\right)=\left\{v_2,v_3,v_5\right\}$ is covered by the clique $S_1=\left\{v_1,v_2,v_3,v_5\right\}$ in ${ℍ}_2$ ;

・ $N_{{ℍ}_4}\left(v_1\right)=\left\{v_3,v_4,v_8\right\}$ is covered by the clique $S_1=\left\{v_1,v_3,v_4,v_8\right\}$ in ${ℍ}_4$ ;

・ $N_{{ℍ}_5}\left(v_1\right)=\left\{v_3,v_4,v_5\right\}$ is covered by the clique $S_1=\left\{v_1,v_3,v_4,v_5\right\}$ in ${ℍ}_5$ ;

・ $N_{{ℍ}_6}\left(v_1\right)=\left\{v_5,v_6,v_7\right\}$ is covered by the clique $S_1=\left\{v_1,v_5,v_6,v_7\right\}$ in ${ℍ}_6$ .

Then we have

${\theta }_v\left(N_{{ℍ}_i}\left(v\right)\right)\ge 2,v\in V\left({ℍ}_i\right),\text{where}i=1,3,$

and

${\theta }_v\left(N_{{ℍ}_i}\left(v_1\right)\right)=1,\text{where}i=2,4,5,6.$

By Theorem 2

$k\left({ℍ}_i\right)\ge \min \left\{{\theta }_v\left(N_{{ℍ}_i}\left(v\right)\right)|v\in V\left({ℍ}_i\right)\right\}\ge \{\begin{array}{ll}2,\hfill & i=1,3;\hfill \\ 1,\hfill & i=2,4,5,6.\hfill \end{array}$ (4)

Combining inequalities (3) and (4) we have

$k\left({ℍ}_i\right)=\{\begin{array}{ll}2,\hfill & i=1,3;\hfill \\ 1,\hfill & i=2,4,5,6.\hfill \end{array}$

4. Triangulation $G\left(n\right)$ of a Sphere

In this section we study a graph $G\left(n\right)=\left(V,E\right)$ with $3n\left(n\ge 2\right)$ vertices, where

$V={\displaystyle \underset{i=1}{\overset{n}{\cup }}}\left\{x_i,y_i,z_i\right\}$

and

$E={\displaystyle \underset{i=1}{\overset{n}{\cup }}}\left\{x_i{y}_i,y_i{z}_i,x_i{z}_i\right\}\cup {\displaystyle \underset{i=1}{\overset{n-1}{\cup }}}\left\{x_i{x}_{i+1},x_i{z}_{i+1},y_i{y}_{i+1},y_i{z}_{i+1},z_i{x}_{i+1},z_i{y}_{i+1}\right\}.$

An example $G\left(3\right)$ is shown in Figure 6(a). In fact, we can draw $G\left(n\right)$ in the plane by the following way. First we draw the triangles $\Delta x_i{y}_i{z}_i\left(i=1,2,\cdots ,n\right)$ such that $\Delta x_{i+1}{y}_{i+1}{z}_{i+1}$ includes $\Delta x_i{y}_i{z}_i$ , and $x_i,y_i,z_i$ are in clockwise order if $i$ is even, or in counter-clockwise order if $i$ is odd, respectively. Then we draw the other edges. It is easy to see that each face of $G\left(n\right)$ is a triangle. So for each $n\ge 2$ , $G\left(n\right)$ is a triangulation of a sphere.

Theorem 7. For each $n\ge 2$ , $k\left(G\left(n\right)\right)=2$ .

Proof. Let $\sigma$ be a vertex ordering of $G\left(n\right)$ such that $\sigma \left(x_i\right)=v_{3i-2}$ ,

$\sigma \left(y_i\right)=v_{3i-1}$ and $\sigma \left(z_i\right)=v_{3i}$ , where $i=1,2,\cdots ,n$ . Let

$\begin{array}{l}{S}_1=\left\{v_1,v_2,v_3\right\},\\ S_{3i-1}=\left\{v_{3i-2},v_{3i+1},v_{3i+3}\right\},\\ S_{3i}=\left\{v_{3i-1},v_{3i+2},v_{3i+3}\right\}\text{and}\\ S_{3i+1}=\left\{v_{3i},v_{3i+1},v_{3i+2}\right\},\text{where}i=1,\cdots ,n-1.\end{array}$

Figure 6. $G\left(3\right)$ and an edge clique cover of $G\left(3\right)$ .

Then the family $\left\{S_1,S_2,\cdots ,S_{3n-2}\right\}$ is an edge clique cover of $G\left(n\right)$ . An edge clique cover of $G\left(3\right)$ is shown in Figure 6(b).

Now, we define a digraph $D$ by the following:

$\begin{array}{l}V\left(D\right)=V\left(G\left(n\right)\right)\cup \left\{a,b\right\},\\ S_1=\left\{v_1,v_2,v_3\right\}\to v_4,\\ S_{3i-1}=\left\{v_{3i-2},v_{3i+1},v_{3i+3}\right\}\to v_{3i+4},\\ S_{3i}=\left\{v_{3i-1},v_{3i+2},v_{3i+3}\right\}\to v_{3i+5},\text{and}\\ S_{3i+1}=\left\{v_{3i},v_{3i+1},v_{3i+2}\right\}\to v_{3i+3},\text{where}i=1,\cdots ,n-1.\end{array}$

Note that $v_{3n+1}=a,v_{3n+2}=b$ are new vertices. Then by Theorem 4 the digraph $D$ is acyclic and $C\left(D\right)=G\left(n\right)\cup \left\{a,b\right\}$ . Hence we have

$k\left(G\left(n\right)\right)\le 2.$ (5)

On the other hand, since $\delta \left(G\left(n\right)\right)=4$ and there is no clique with more than 3 vertices in $G\left(n\right)$ , then by Theorem 2

$k\left(G\left(n\right)\right)\ge \min \left\{{\theta }_v\left(N_{G\left(n\right)}\left(v\right)\right)|v\in V\left(G\left(n\right)\right)\right\}\ge 2.$ (6)

Combining inequalities (5) and (6) we have $k\left(G\left(n\right)\right)=2$ .

5. Closing Remarks

In this paper, we provide the exact values of the competition numbers of a 24-hedron, a class of dodecahedra and a triangulation of a sphere with

$3n\left(n\ge 2\right)$ vertices. It would be interesting to compute the competition numbers of some other triangulations of a sphere.

For a digraph $D=\left(V,A\right)$ , if we partition $V$ into $k$ types, then we may construct a undirected graph $C^k\left(D\right)=\left(V,E\right)$ of $D$ as follows:

1) $uv\in E$ if and only if there exists some vertex $x\in V$ such that

$\left(u,x\right),\left(v,x\right)\in A$ and $u\mathrm{,}v$ are of the same type, or

2) $uv\in E$ if and only if there exists some vertex $x\in V$ such that

$\left(u,x\right),\left(v,x\right)\in A$ and $u\mathrm{,}v$ are of different types.

It is easy to see that $C^1\left(D\right)=C\left(D\right)$ for a given digraph $D$ , and we note that multitype graphs can be used to study the multi-species in ecology and have been deeply studied (see [26] [27] ). So these generalizations of competition graphs may be more realistic and more interesting.

Acknowledgements

We thank the editor and the referee for their valuable comments. The work was supported in part by the Natural Science Foundation of Hebei Province of China under Grant A2015106045, and in part by the Institute of Applied Mathematics of Shijiazhuang University.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Cohen, J.E. (1968) Interval Graphs and Food Webs: A Finding and a Problem, Document 17696-PR, RAND Corporation, Santa Monica, CA.
[2]	Roberts, F.S. (1978) Food Webs, Competition Graphs, and the Boxicity of Ecological Phase Space. In: Alavi, Y. and Lick, D., Eds., Theory and Applications of Graphs (International Proceding Conference, Western Michigan University, Kalamazoo, Michigan, 1976), 477-490. https://doi.org/10.1007/bfb0070404
[3]	Opsut, R.J. (1982) On the Computation of the Competition Number of a Graph. SIAM Journal on Algebraic Discrete Methods, 3, 420-428. https://doi.org/10.1137/0603043
[4]	Kim, S. R. and Roberts, F.S. (1997) Competition Numbers of Graphs with a Small Number of Triangles. Discrete Applied Mathematics, 78, 153-162. https://doi.org/10.1016/S0166-218X(97)00026-7
[5]	Sano, Y. (2009) The Competition Numbers of Regular Polyhedra. Congressus Numerantium, 198, 211-219. https://doi.org/10.7151/dmgt.1506
[6]	Kim, S.R., Park, B. and Sano, Y. (2010) The Competition Numbers of Johnson Graphs. Discussiones Mathematicae Graph Theory, 30, 449-459.
[7]	Park, B. and Sano, Y. (2011) The Competition Numbers of Hamming Graphs with Diameter at Most Three. Journal of the Korean Mathematical Society, 48, 691-702. https://doi.org/10.4134/JKMS.2011.48.4.691
[8]	Park, B. and Sano, Y. (2011) The Competition Numbers of Ternary Hamming Graphs. Applied Mathematics Letters, 24, 1608-1613. https://doi.org/10.1016/j.aml.2011.04.012
[9]	Kim, S.R., Park, B. and Sano, Y. (2013) The Competition Number of the Complement of a Cycle. Discrete Applied Mathematics, 161, 1755-1760. https://doi.org/10.1016/j.dam.2011.10.034
[10]	Kim, S.R., Park, B. and Sano, Y. (2012) The Competition Numbers of Complete Multipartite Graphs with Many Partite Sets. Discrete Applied Mathematics, 160, 1176-1182. https://doi.org/10.1016/j.dam.2011.12.017
[11]	Kim, S.R. and Sano, Y. (2008) The Competition Numbers of Complete Tripartite Graphs. Discrete Applied Mathematics, 156, 3522-3524. https://doi.org/10.1016/j.dam.2008.04.009
[12]	Kuhl, J. (2013) Transversals and Competition Numbers of Complete Multipartite Graphs. Discrete Applied Mathematics, 161, 435-440. https://doi.org/10.1016/j.dam.2012.09.012
[13]	Li, B.J. and Chang, G.J. (2012) Competition Numbers of Complete -Partite Graphs. Discrete Applied Mathematics, 160, 2271-2276. https://doi.org/10.1016/j.dam.2012.05.005
[14]	Park, B., Kim, S.R. and Sano, Y. (2009) The Competition Numbers of Complete Multipartite Graphs and Mutually Orthogonal Latin Squares. Discrete Mathematics, 309, 6464-6469. https://doi.org/10.1016/j.disc.2009.06.016
[15]	Cho, H.H. and Kim, S.R. (2005) The Competition Number of a Graph Having Exactly One Hole. Discrete Mathematics, 303, 32-41. https://doi.org/10.1016/j.disc.2004.12.016
[16]	Kamibeppu, A. (2012) A Sufficient Condition for Kim’s Conjecture on the Competition Numbers of Graphs. Discrete Mathematics, 312, 1123-1127. https://doi.org/10.1016/j.disc.2011.11.035
[17]	Kamibeppu, A. (2010) An Upper Bound for the Competition Numbers of Graphs. Discrete Applied Mathematics, 158, 154-157. https://doi.org/10.1016/j.dam.2009.09.007
[18]	Kim, S.R. (2005) Graphs with One Hole and Competition Number One. Journal of the Korean Mathematical Society, 42, 1251-1264. https://doi.org/10.4134/JKMS.2005.42.6.1251
[19]	Kim, S.R., Lee, J.Y., Park, B. and Sano, Y. (2012) The Competition Number of a Graph and the Dimension of Its Hole Space. Applied Mathematics Letters, 25, 638-642. https://doi.org/10.1016/j.aml.2011.10.003
[20]	Kim, S.R., Lee, J.Y. and Sano, Y. (2010) The Competition Number of a Graph Whose Holes Do Not Overlap Much. Discrete Applied Mathematics, 158, 1456-1460. https://doi.org/10.1016/j.dam.2010.04.004
[21]	Lee, J.Y., Kim, S.R., Kim, S.J. and Sano, Y. (2011) Graphs Having Many Holes But with Small Competition Numbers. Applied Mathematics Letters, 24, 1331-1335. https://doi.org/10.1016/j.aml.2011.03.003
[22]	Lee, J.Y., Kim, S.R., Kim, S.J. and Sano, Y. (2010) The Competition Number of a Graph with Exactly Two Holes. Ars Combinatoria, 95, 45-54.
[23]	Li, B.J. and Chang, G.J. (2009) The Competition Number of a Graph with Exactly h Holes, All of Which Are Independent. Discrete Applied Mathematics, 157, 1337-1341. https://doi.org/10.1016/j.dam.2008.11.004
[24]	Sano, Y. (2013) A Generalization of Opsut’s Lower Bounds for the Competition Number of a Graph. Graphs and Combinatorics, 29, 1543-1547. https://doi.org/10.1007/s00373-012-1188-5
[25]	Harary, F., Norman, R.Z. and Cartwright, D. (1965) Structure Models: An Introduction to the Theory of Directed Graphs, Wiley, New York.
[26]	Barbour, A.D. and Reinert, G. (2011) The Shortest Distance in Random Multi-Type Intersection Graphs. Random Structures & Algorithms, 39, 179-209. https://doi.org/10.1002/rsa.20351
[27]	Shang, Y. (2016) Groupies in Multitype Random Graphs. SpringerPlus, 5, 989. https://doi.org/10.1186/s40064-016-2705-4