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\mathrm{,}x\right)\mathrm{,}\left(v\mathrm{,}x\right)\in A\left(D\right)$ . We say that a graph $G$ is a competition graph if there exists a digraph $D$ such that $C\left(D\right)=G$ .

*Corresponding author.

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 appear. 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] - [21] ) 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 denoted by $N_G\left(v\right)=\left\{u|u\text{is}\text{adjacent}\text{to}v\right\}$ . For any set $S$ of vertices in $G$ , we define the neighborhood of $S$ in $G$ to be the set of all vertices adjacent to vertices in $S$ , this set is denoted by $,v_1\},$

$C\left(D_2\right)=V\left(G\right)\cup \left\{v_0\right\}\cup \left\{y_1^1,y_2^2,\cdots ,y_{{\beta }_1}^1\right\}\text{and}$

$C\left(D_3\right)=G\cup \left\{v_0\right\}\cup {\displaystyle \underset{1\le i\le k,{\beta }_i>0}{\cup }}\left\{y_1^i,y_2^i,\cdots ,y_{{\beta }_i}^i\right\}.$

And we know that $V_1\left(C\right)=\left\{x_1^1,x_2^2,\cdots ,x_{{\beta }_1}^1\right\}$ if $V_2\left(C\right)=\varnothing$ , and

$V_1\left(C\right)={\displaystyle \underset{1\le i\le k,{\beta }_i>0}{\cup }}\left\{x_1^i,x_2^i,\cdots ,x_{{\beta }_i}^i\right\}$ if $V_1\left(C\right)\ne \varnothing$ and $V_2\left(C\right)\ne \varnothing$ . So the result follows. $\square$

Lemma 4. For any not $K_4$ generalized Halin graph $G=T\cup C$ ,

$\left|V_1\left(C\right)\right|={\theta }_e\left(G\right)-\left|V\left(G\right)\right|+1.$

Proof. Let $G=T\cup C$ be a not $K_4$ generalized Halin graph, where $T$ and $C$ are the characteristic tree and the adjoint cycle of $G$ , respectively. Since $G\left[V\left(G\right)\backslash V\left(C\right)\right]$ is a tree, then ${\theta }_e\left(G\left[V\left(G\right)\backslash V\left(C\right)\right]\right)=\left|V\left(G\right)\right|-\left|V\left(C\right)\right|-1$ . Note that $G\left[V\left(C\right)\cup {V^{\prime }}_2\right]$ just includes all triangles in $G$ and the edges in $C$ , so ${\theta }_e\left(G\left[V\left(C\right)\cup {V^{\prime }}_2\right]\right)=\left|V\left(C\right)\right|$ . It is easy to check that ${\theta }_e\left(G\left[V_1\left(C\right)\cup {V^{\prime }}_1\right]\right)=\left|V_1\left(C\right)\right|$ . Furthermore, each pair of graphs $G\left[V\left(G\right)\backslash V\left(C\right)\right]$ , $G\left[V\left(C\right)\cup {V^{\prime }}_2\right]$ and $G\left[V_1\left(C\right)\cup {V^{\prime }}_1\right]$ has not any common edges. So we have

$\begin{array}{c}{\theta }_e\left(G\right)={\theta }_e\left(G\left[V\left(G\right)\backslash V\left(C\right)\right]\right)+{\theta }_e\left(G\left[V\left(C\right)\cup {V^{\prime }}_2\right]\right)+{\theta }_e\left(G\left[V_1\left(C\right)\cup {V^{\prime }}_1\right]\right)\\ =\left(\left|V\left(G\right)\right|-\left|V\left(C\right)\right|-1\right)+\left|V\left(C\right)\right|+\left|V_1\left(C\right)\right|\\ =\left|V\left(G\right)\right||+\left|V_1\left(C\right)\right|-1\end{array}$

or

$\left|V_1\left(C\right)\right|={\theta }_e\left(G\right)-\left|V\left(G\right)\right|+1.$ $\square$

3. Pseudo-Halin Graph

Now we consider a pseudo-Halin graph $G$ with the exterior face $f_0$ and $I\left(f_0\right)=\left\{x\right\}$ . Let $u$ and $v$ be the neighbors of $x$ on the boundary of $f_0$ . Without lose of generality, we may always assume that $u$ is on the left of $x$ and $v$ on the right of $x$ . Let $G^{\prime }=G-\left\{xu,xv\right\}+uv$ . Note that $G^{\prime }$ is a generalized Halin graph since $d_{G^{\prime }}\left(x\right)\ge 2$ is accepted. See Figure 1. Let $G^{\prime }=T\cup C^{\prime }$ , where $T$ and $C^{\prime }$ are the characteristic tree and the adjoint cycle of $G^{\prime }$ , respectively. Then it is easy to see that $C^{\prime }$ is got from the boundary of $f_0$ by deleting the edges $xu$ and $xv$ , and adding the edge $uv$ . So we have $V\left(C^{\prime }\right)=R\left(f_0\right)$ . Let $b\ne x$ be another neighbor of $u$ on cycle $C^{\prime }$ . The characteristic tree $T$ of $G^{\prime }$ is just the tree got from $G$ by deleting the edges on the boundary of the face $f_0$ . So $T$ may also be called the characteristic tree of $G$ . Let $u^{\prime }$ be the neighbor of $u$ in $T$ and $v^{\prime }$ the neighbor of $v$ in $T$ , respectively.

We construct a graph $G^{″}$ from $G^{\prime }$ by replacing the edge $uv$ by a path $u{x}^{\prime }v$ , and joining $x$ with $x^{\prime }$ . It is not difficult to see that $G^{″}$ is a Halin graph. Since every Halin graph contains a triangle, and $x^{\prime }$ is not a vertex of any triangle in $G^{″}$ , then $G^{\prime }$ also contains a triangle. Therefore $V_2\left(C^{\prime }\right)\ne \varnothing$ . So we just need to consider the following cases.

Theorem 3. Let $G$ be a pseudo-Halin graph with $I\left(f_0\right)=\left\{x\right\}$ , and $C^{\prime }$ the adjoint cycle of graph $G^{\prime }=G-\left\{xu,xv\right\}+uv$ . If $V_1\left(C^{\prime }\right)=\varnothing$ , then $k\left(G\right)=2$ .

Proof. Suppose that G is a pseudo-Halin graph with $I\left(f_0\right)=\left\{x\right\}$ and $V_1\left(C^{\prime }\right)=\varnothing$ , where $C^{\prime }$ is the adjoint cycle of graph $G^{\prime }=G-\left\{xu,xv\right\}+uv$ . Denote and labelling the vertices of $G^{\prime }$ in a similar way as used in Lemma 3. By Lemma 3, $k\left(G^{\prime }\right)\le 2$ . Let $v=v_1^1$ and by the similar way used in the proof of Lemma 3, there is a digraph $D^{\prime }$ such that

$C\left(D^{\prime }\right)=G^{\prime }\cup \left\{v_0,v_1\right\},$

and

$\left\{\left(v,v_0\right),\left(v^{\prime },v_0\right),\left(u,v_1\right),\left(v,v_1\right),\left(u,b\right)\right\}\subset A\left(D^{\prime }\right)$

but

$\left(u^{\prime }\mathrm{,}b\right)\notin A\left(D^{\prime }\right)\mathrm{,}$

where $v_0$ and $v_1$ are two isolated vertices not in $G^{\prime }$ . Note that $N_{D^{\prime }}^{-}\left(b\right)=\left\{u\right\}$ . Let

$V\left(D\right)=V\left(D^{\prime }\right)$

and

$A\left(D\right)=A\left(D^{\prime }\right)\cup \left\{\left(x,b\right),\left(x,v_1\right)\right\}\backslash \left\{\left(u,v_1\right)\right\}.$

See Figure 2. Note that $D$ is acyclic since every arc added here goes from a big label vertex to a small label vertex. It is easy to see that $C\left(D\right)=G\cup \left\{v_0,v_1\right\}\mathrm{.}$ So we have $k\left(G\right)\le 2$ . On the other hand, since for each vertex $v\in V\left(G\right)$ , $d_G\left(v\right)\ge 3$ , and note that the maximal clique in $G$ is a triangle, so we have ${\theta }_v\left(N_G\left(v\right)\right)\ge 2$ . By Theorem 2, $k\left(G\right)\ge \min \left\{{\theta }_v\left(N_G\left(v\right)\right)|v\in V\left(G\right)\right\}\ge 2$ . Therefore $k\left(G\right)=2$ . $\square$

Lemma 5. Let $G$ be a pseudo-Halin graph with $I\left(f_0\right)=\left\{x\right\}$ , and $C^{\prime }$ the adjoint cycle of graph $G^{\prime }=G-\left\{xu,xv\right\}+uv$ . If $V_1\left(C^{\prime }\right)\ne \varnothing$ , then we have $k\left(G\right)\le \left|V_1\left(C^{\prime }\right)\right|+2$ .

Proof. Suppose that $G$ is a pseudo-Halin graph with $I\left(f_0\right)=\left\{x\right\}$ and $V_1\left(C^{\prime }\right)\ne \varnothing$ , where $C^{\prime }$ is the adjoint cycle of graph $G^{\prime }=G-\left\{xu,xv\right\}+uv$ . Denote and labelling the vertices of $G^{\prime }$ in a similar way as used in Lemma 3. By Lemma 3,

$k\left(G^{\prime }\right)\le \left|V_1\left(C^{\prime }\right)\right|+1$ , and there is a digraph $D^{\prime }$ such that $C\left(D^{\prime }\right)=G^{\prime }\cup I_{\left|V_1\left(C^{\prime }\right)\right|+1}$ , where $I_{\left|V_1\left(C^{\prime }\right)\right|+1}$ are $\left|V_1\left(C^{\prime }\right)\right|+1$ isolated vertices not in $G^{\prime }$ . By the similar way used in the proof of Lemma 3, there exists a vertex $y\in I_{\left|V_1\left(C^{\prime }\right)\right|+1}$ or $y\in V\left(C^{\prime }\right)$ such that $uy\mathrm{,}vy\in A\left(D^{\prime }\right)$ . Let

$V\left(D\right)=V\left(D^{\prime }\right)\cup \left\{w\right\}$

and

$A\left(D\right)=A\left(D^{\prime }\right)\cup \left\{\left(x,w\right),\left(u,w\right),\left(x,y\right)\right\}\backslash \left\{\left(u,y\right)\right\},$

where $w$ is a new added vertex to $D^{\prime }$ . Note that $D$ is acyclic since every arc added here goes from a big label vertex to a small label vertex or to a new added vertex. It is

easy to see that $C\left(D\right)=G\cup I_{\left|V_1\left(C^{\prime }\right)\right|+1}\cup \left\{w\right\}$ . So we have $k\left(G\right)\le \left|V_1\left(C^{\prime }\right)\right|+2$ . $\square$

Lemma 6. Let $G$ be a pseudo-Halin graph with $I\left(f_0\right)=\left\{x\right\}$ , and $C^{\prime }$ the adjoint cycle of graph $G^{\prime }=G-\left\{xu,xv\right\}+uv$ .

1) If $x{u}^{\prime }\mathrm{,}x{v}^{\prime }\notin E\left(G\right)$ , then ${\theta }_e\left(G^{\prime }\right)={\theta }_e\left(G\right)-1$ ,

2) If $x{u}^{\prime }\mathrm{,}x{v}^{\prime }\in E\left(G\right)$ , then ${\theta }_e\left(G^{\prime }\right)=\{\begin{array}{ll}{\theta }_e\left(G\right)+3,\hfill & u,v\in V_1\left(C^{\prime }\right);\hfill \\ {\theta }_e\left(G\right)+1,\hfill & u,v\in V_2\left(C^{\prime }\right);\hfill \\ {\theta }_e\left(G\right)+2,\hfill & \text{otherwise,}\hfill \end{array}$

3) If $x{p}^{\prime }\in E\left(G\right)$ , but $x{q}^{\prime }\notin E\left(G\right)$ , then ${\theta }_e\left(G^{\prime }\right)=\{\begin{array}{ll}{\theta }_e\left(G\right)+1,\hfill & p\in V_1\left(C^{\prime }\right);\hfill \\ {\theta }_e\left(G\right),\hfill & p\in V_2\left(C^{\prime }\right),\hfill \end{array}$ where

$\left\{p,q\right\}=\left\{u,v\right\}$ .

Proof. 1) $x{u}^{\prime }\mathrm{,}x{v}^{\prime }\notin E\left(G\right)$ .

Obviously, $\left\{x\mathrm{,}u\right\}$ and $\left\{x\mathrm{,}v\right\}$ are two maximal cliques of $G$ . Since $\left\{u\mathrm{,}v\right\}$ is a maximal clique of $G^{\prime }$ , then ${\theta }_e\left(G^{\prime }\right)={\theta }_e\left(G\right)-1$ .

2) $x{u}^{\prime }\mathrm{,}x{v}^{\prime }\in E\left(G\right)$ .

It is easy to see that $\left\{x\mathrm{,}u\mathrm{,}{u}^{\prime }\right\}$ and $\left\{x\mathrm{,}v\mathrm{,}{v}^{\prime }\right\}$ are two maximal cliques of $G$ . Note that $uv$ is a maximal clique of $G^{\prime }$ . If $u\mathrm{,}v\in V_1\left(C^{\prime }\right)$ , then $\left\{x\mathrm{,}{u}^{\prime }\right\}$ , $\left\{u\mathrm{,}{u}^{\prime }\right\}$ , $\left\{x\mathrm{,}{v}^{\prime }\right\}$ and $\left\{v\mathrm{,}{v}^{\prime }\right\}$ are all maximal cliques of graph $G^{\prime }$ . So ${\theta }_e\left(G^{\prime }\right)={\theta }_e\left(G\right)+3$ ; If $u\mathrm{,}v\in V_2\left(C^{\prime }\right)$ , then $\left\{x\mathrm{,}{u}^{\prime }\right\}$ and $\left\{x\mathrm{,}{v}^{\prime }\right\}$ are two maximal cliques of graph $G^{\prime }$ , but $\left\{u\mathrm{,}{u}^{\prime }\right\}$ and $\left\{v\mathrm{,}{v}^{\prime }\right\}$ not. Hence ${\theta }_e\left(G^{\prime }\right)={\theta }_e\left(G\right)+1$ ; Otherwise, say $u\in V_1\left(C^{\prime }\right)$ and $v\in V_2\left(C^{\prime }\right)$ . Then $\left\{x\mathrm{,}{u}^{\prime }\right\}$ , $\left\{u\mathrm{,}{u}^{\prime }\right\}$ and $\left\{x\mathrm{,}{v}^{\prime }\right\}$ are all maximal cliques of graph $G^{\prime }$ , but $\left\{v\mathrm{,}{v}^{\prime }\right\}$ not. Therefore ${\theta }_e\left(G^{\prime }\right)={\theta }_e\left(G\right)+\text{2}$ .

3) $x{u}^{\prime }\in E\left(G\right)$ but $x{v}^{\prime }\notin E\left(G\right)$ (or $x{v}^{\prime }\in E\left(G\right)$ but $x{u}^{\prime }\notin E\left(G\right)$ ).

Without lose of generality, we just need to consider the case $x{u}^{\prime }\in E$ but $x{v}^{\prime }\notin E$ . By the proof of Case (1), ${\theta }_e\left(G-xu+uv\right)={\theta }_e\left(G\right)$ . If $v\in V_1\left(C^{\prime }\right)$ , then $\left\{x\mathrm{,}{v}^{\prime }\right\}$ and $\left\{v\mathrm{,}{v}^{\prime }\right\}$ are all maximal cliques of graph $G^{\prime }$ . If $v\in V_2\left(C^{\prime }\right)$ , then $\left\{x\mathrm{,}{v}^{\prime }\right\}$ is a maximal clique of graph $G^{\prime }$ , but $\left\{v\mathrm{,}{v}^{\prime }\right\}$ not. So the result follows. $\square$

For a pseudo-Halin graph $G$ , suppose that $f_0$ be the exterior face of $G$ and $I\left(f_0\right)=\left\{x\right\}$ . Note that $G^{\prime }$ can not be $K_4$ , so by Lemmas 4 we have

$\left|V_1\left(C^{\prime }\right)\right|={\theta }_e\left(G^{\prime }\right)-\left|V\left(G\right)\right|+1$ , by Lemma 5 we have $k\left(G\right)\le \left|V_1\left(C^{\prime }\right)\right|+2\le {\theta }_e\left(G^{\prime }\right)-\left|V\left(G\right)\right|+3$ . On the other hand, by Theorem 1 we have $k\left(G\right)\ge {\theta }_e\left(G\right)-\left|V\left(G\right)\right|+2$ . So by lemmas 6, we have the following result.

Theorem 4. Let $G$ be a pseudo-Halin graph with $I\left(f_0\right)=\left\{x\right\}$ and $V_1\left(C^{\prime }\right)\ne \varnothing$ , where $C^{\prime }$ is the adjoint cycle of graph $G^{\prime }=G-\left\{xu,xv\right\}+uv$ .

1) If $x{u}^{\prime },x{v}^{\prime }\notin E$ , then $k\left(G\right)={\theta }_e\left(G\right)-\left|V\left(G\right)\right|+2$ ,

2) If $x{u}^{\prime }\mathrm{,}x{v}^{\prime }\in E$ , then

${\theta }_e\left(G\right)-\left|V\left(G\right)\right|+2\le k\left(G\right)\le \{\begin{array}{ll}{\theta }_e\left(G\right)-\left|V\left(G\right)\right|+6,\hfill & u,v\in V_1\left(C^{\prime }\right);\hfill \\ {\theta }_e\left(G\right)-\left|V\left(G\right)\right|+4,\hfill & u,v\in V_2\left(C^{\prime }\right);\hfill \\ {\theta }_e\left(G\right)-\left|V\left(G\right)\right|+5,\hfill & \text{otherwise},\hfill \end{array}$

3) If $x{p}^{\prime }\in E$ , and $x{q}^{\prime }\notin E$ , then

${\theta }_e\left(G\right)-\left|V\left(G\right)\right|+2\le k\left(G\right)\le \{\begin{array}{ll}{\theta }_e\left(G\right)-\left|V\left(G\right)\right|+4,\hfill & p\in V_1\left(C^{\prime }\right);\hfill \\ {\theta }_e\left(G\right)-\left|V\left(G\right)\right|+3,\hfill & p\in V_2\left(C^{\prime }\right),\hfill \end{array}$

where $\left\{p,q\right\}=\left\{u,v\right\}$ .

4. Concluding Remarks

In this paper, we study the competition numbers of a kind of pseudo-Halin graphs with just one irregular vertex.

For a pseudo-Halin graph $G$ with the exterior face $f_0$ and $\left|I\left(f_0\right)\right|=1$ , we show that if all leaves of the characteristic tree of $G$ are compound leaves, then $k\left(G\right)=2$ , otherwise, ${\theta }_e\left(G\right)-\left|V\left(G\right)\right|+2\le k\left(G\right)\le {\theta }_e\left(G\right)-\left|V\left(G\right)\right|+6$ . Even we proved that $k\left(G\right)={\theta }_e\left(G\right)-\left|V\left(G\right)\right|+2$ for some cases, but we can not provide the accurate value of the competition number of $G$ for other cases. So it would be valuable to get the accurate value of the competition number of the pseudo-Halin graph with just one irregular vertex, and it may be interesting to study the competition numbers of general pseudo-Halin graphs.

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\mathrm{,}x\right)\mathrm{,}\left(v\mathrm{,}x\right)\in A$ and $u\mathrm{,}v$ are of same type, or

2) $uv\in E$ if and only if there exists some vertex $x\in V$ such that $\left(u\mathrm{,}x\right)\mathrm{,}\left(v\mathrm{,}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 [23] [24] . 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.