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 $N_G\left(S\right)$ . An in-neighbor of a vertex $v$ in digraph $D$ is a vertex $u$ such that $\left(u\mathrm{,}v\right)\in A\left(D\right)$ ; an out-neighbor of a vertex $v$ is a vertex $w$ such that $\left(v\mathrm{,}w\right)\in A\left(D\right)$ . We denote the sets of in-neighbors and out-neighbors of $v$ in $D$ by $N_D^{-}\left(v\right)$ and $N_D^{+}\left(v\right)$ , re- spectively.

A subset $S$ of the vertex set of a graph $G$ is called a clique of $G$ if $G\left[S\right]$ is a complete graph. For a clique $S$ of a graph $G$ and an edge $e$ of $G$ , we say $e$ is covered by $S$ if both of the endpoints of $e$ are contained in $S$ . 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$ .

A generalized Halin graph $G=T\cup C$ is a plane graph consisting of a plane embedding of a tree $T$ and a cycle $C$ connecting the leaves (vertices of degree 1) of $T$ such that $C$ is the boundary of the exterior face. The tree $T$ and the cycle $C$ are called the characteristic tree and the adjoint cycle of $G$ , respectively. For each $v\in V\left(C\right)$ , if $N_T\left(v\right)\cap N_T\left(x\right)=\varnothing$ for any vertex $x\in N_C\left(v\right)$ , then we called $v$ a simple leaf of $T$ , otherwise, a compound leaf of $T$ . Denote all simple leaves of $T$ by $V_1\left(C\right)$ and all compound leaves of $T$ by $V_2\left(C\right)$ , respectively. It is obvious that $V\left(C\right)=V_1\left(C\right)\cup V_2\left(C\right)$ , and $V_1\left(C\right)\cap V_2\left(C\right)=\varnothing$ . Let ${V^{\prime }}_1=N_T\left(V_1\left(C\right)\right)$ , ${V^{\prime }}_2=N_T\left(V_2\left(C\right)\right)$ . A generalized Halin graph $G$ is a Halin graph when each interior vertex of $G$ has degree at least 3.

A 2-connected planar graph $G$ with minimum degree at least 3 is a pseudo-Halin graph if deleting the edges on the boundary of a single face $f_0$ yields a tree. It is a Halin graph if the vertices of $f_0$ all have degree 3 in $G$ . The face $f_0$ is the exterior face; the others are interior faces. Vertices of $f_0$ are exterior vertices; the others are interior vertices. Vertices of $f_0$ with degree 3 in $G$ are regular vertices; the others are irregular vertices. Let $R\left(f_0\right)$ and $I\left(f_0\right)$ denote the sets of regular and irregular vertices in $f_0$ , respectively.

The main theme of this paper is to study the competition numbers of a kind of pseudo-Halin graphs with $\left|I\left(f_0\right)\right|=1$ , and gets the exact value or the upper bound of the competition number of this kind of pseudo-Halin graphs.

2. Lemmas

We first introduce two useful Lemmas.

Lemma 1 (Harary et al. [22] ). 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\mathrm{,}j\in \left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ , $\left(v_i\mathrm{,}{v}_j\right)\in A$ implies that $i<j$ ;

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

By this lemma, if $D$ is an acyclic digraph, we can find a vertex labelling $\sigma \mathrm{<mo>\; :\; </mo>}V\to \left\{\mathrm{1,2,}\cdots \mathrm{,}\left|V\right|\right\}$ so that whenever $\left(x\mathrm{,}y\right)\in A$ , $\sigma \left(y\right)\mathrm{<mo>\; <\; </mo>}\sigma \left(x\right)$ . We call $\sigma$ an acyclic labelling of $D$ . Conversely, if $D$ is a digraph with an acyclic labelling, then $D$ is acyclic.

Lemma 2 (Kim and Roberts [4] ). For a tree $T$ and a vertex $v$ of $T$ , there is an acyclic digraph $D$ so that $T\cup \left\{v_0\right\}$ is the competition graph of $D$ for $v_0$ not in $T$ and so that $v$ has only outgoing arcs in $D$ .

Kim and Roberts [4] proved Lemma 2 by the following algorithm.

Let $T_1=T$ , $V\left(D_1\right)=V\left(T\right)$ , and $A\left(D_1\right)=\varnothing$ . Choose a vertex $v_1$ of degree 1 from $T_1$ . If $v^1$ is adjacent to $v_1$ in $T_1$ , let $T_2=T-v_1$ , $V\left(D_2\right)=V\left(D_1\right)\cup \left\{v_0\right\}$ for some vertex $v_0$ not in $T$ , and $A\left(D_2\right)=\left\{\left(v_1,v_0\right),\left(v^1,v_0\right)\right\}$ . Having defined $T_i$ and $D_i$ , choose a vertex $v_i$ of degree 1 from $T_i$ . If $v^i$ is adjacent to $v_i$ in $T_i$ , then let $T_{i+1}=T_i-v_i$ , $V\left(D_{i+1}\right)=V\left(D_i\right)$ , and $A\left(D_{i+1}\right)=A\left(D_i\right)\cup \left\{\left(v_i,v_{i-1}\right),\left(v^i,v_{i-1}\right)\right\}$ . Repeat this last step until $D_n$ has been defined. Let $D=\left(V\left(D_n\right),A\left(D_n\right)\right)$ . In the procedure, we may avoid selecting $v$ until we select all other vertices since there are at least two vertices of degree 1 in a tree with more than one vertex.

In fact, this algorithm provides an acyclic labelling $\sigma =\left[v_0,v_1,v_2,\cdots ,v_n\right]$ of $D$ such that $v_n=v^{n-1}$ , $v_{n-1}{v}_n\in E\left(T\right)$ , and $v_{n-1}$ and $v_n$ have only outgoing arcs in $D$ , where $\left|V\left(T\right)\right|=n$ .

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\}$ .

Lemma 3. For any generalized Halin graph $G=T\cup C$ ,

$k\left(G\right)\le \{\begin{array}{ll}2,\hfill & V_1\left(C\right)=\varnothing ;\hfill \\ \left|V_1\left(C\right)\right|+1,\hfill & V_1\left(C\right)\ne \varnothing .\hfill \end{array}$

Proof. Let $G=T\cup C$ be a generalized Halin graph, where $T$ and $C$ are the characteristic tree and the adjoint cycle of $G$ , respectively. Suppose that along cycle $C$ by clockwise order we can partition $V_2\left(C\right)$ (if $V_2\left(C\right)\ne \varnothing$ ) into $k\ge 1$ subsets $V_2^i\left(C\right)$ such that $V_2\left(C\right)={\cup }_{i=1}^k{V}_2^i\left(C\right)$ and the vertices in each $V_2^i\left(C\right)$ are con- secutive on $C$ , where $1\le i\le k$ . Let $u^i$ be the common neighbor of the vertices in $V_2^i\left(C\right)$ , where $1\le i\le k$ . We assume that the vertices in $V_2^i\left(C\right)$ by clockwise order are $v_1^i\mathrm{,}{v}_2^i\mathrm{,}\cdots \mathrm{,}{v}_{{\alpha }_i}^i$ , where ${\alpha }_i\ge 2$ and $1\le i\le k$ . Denote all vertices on $C$ between $v_{{\alpha }_i}^i$ and $v_1^{i+1}$ by $V_1^i\left(C\right)$ , where $1\le i\le k$ and $v_1^{k+1}=v_1^1$ . We assume that the vertices in $V_1^i\left(C\right)$ (if $V_1^i\left(C\right)\ne \varnothing$ ) by clockwise order are $x_1^i,x_2^i,\cdots ,x_{{\beta }_i}^i$ , where ${\beta }_i\ge 1$ and $i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}k\right\}$ . Note that $V_1\left(C\right)={\cup }_{i=1}^k{V}_1^i\left(C\right)$ , and if $V_1\left(C\right)\ne \varnothing$ then we always let $V_1^k\left(C\right)\ne \varnothing$ . If $V_2\left(C\right)=\varnothing$ , then let $V_1^1\left(C\right)=V\left(C\right)$ and arbitrarily select a vertex in $V\left(C\right)$ as $x_1^1$ .

By Lemma 1 and the algorithm in the proof of Lemma 2, we can construct an acyclic digraph $D$ so that $T\cup \left\{v_0\right\}$ is the competition graph of $D$ for $v_0$ not in $T$ , and get an acyclic labelling

$\sigma :V\cup \left\{v_0\right\}\to \left\{1,2,\cdots ,\left|V\right|+1\right\}$

of $D$ so that

$\sigma \left(v_0\right)=1;$

$\sigma \left(v_j^i\right)=1+{\displaystyle \underset{k=1}{\overset{i-1}{\sum }}}\left({\alpha }_k+{\beta }_k\right)+j,\text{where}1\le i\le k\text{and}1\le j\le {\alpha }_i;$

$\sigma \left(x_j^i\right)=1+{\displaystyle \underset{k=1}{\overset{i}{\sum }}}{\alpha }_k+{\displaystyle \underset{k=1}{\overset{i-1}{\sum }}}{\beta }_k+j,\text{where}1\le i\le k\text{and}1\le j\le {\beta }_i\mathrm{.}$

Note that, if $V_2\left(C\right)=\varnothing$ , then let ${\alpha }_1=0$ , if $V_1^i=\varnothing$ , then let ${\beta }_i=0$ , where

$i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}k\right\}$ , and we always have ${\displaystyle {\sum }_{k=1}^0}\left({\alpha }_k+{\beta }_k\right)=0$ and ${\displaystyle {\sum }_{k=1}^0}{\beta }_k=0$ . Label the

other vertices of $T$ arbitrarily.

Case 1. $V_1\left(C\right)=\varnothing$ .

Let $D_1$ be a digraph whose vertex set is

$V\left(G\right)\cup \left\{v_0\mathrm{,}{v}_1\right\}$

and whose arc set is

$\begin{array}{c}A\left(D\right)\cup {\displaystyle \underset{i=1}{\overset{k}{\cup }}}{\displaystyle \underset{j=2}{\overset{{\alpha }_i}{\cup }}}\left\{\left(v_j^i,v_{j-2}^i\right)\right\}\cup {\displaystyle \underset{i=1}{\overset{k-1}{\cup }}}\left\{\left(v_1^{i+1},v_{{\alpha }_i-1}^i\right)\right\}\\ \cup \left\{\left(v_1^1,v_1\right),\left(v_{{\alpha }_k}^k,v_1\right)\right\}-{\displaystyle \underset{i=1}{\overset{k}{\cup }}}\left\{\left(u^i,v_{{\alpha }_i-1}^i\right)\right\},\end{array}$

where $v_0^1=v_0$ , $v_0^i=v_{{\alpha }_{i-1}}^{i-1}$ for each $i\in \left\{\mathrm{2,3,}\cdots \mathrm{,}k\right\}$ , and $v_0\mathrm{,}{v}_1$ are new added vertices.

Case 2. $V_2\left(C\right)=\varnothing$ .

Let $D_2$ be a digraph whose vertex set is

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

and whose arc set is

$A\left(D\right)\cup {\displaystyle \underset{j=1}{\overset{{\beta }_1}{\cup }}}\left\{\left(x_j^1,y_j^1\right),\left(x_{j+1}^1,y_j^1\right)\right\},$

where $x_{{\beta }_{\text{1}}+1}^1=x_1^1$ , and all $y_j^1$ $\left(1\le j\le {\beta }_1\right)$ are new added vertices.

Case 3. $V_1\left(C\right)\ne \varnothing$ and $V_2\left(C\right)\ne \varnothing$ .

Let $D_3$ be a digraph whose vertex set is

$V\left(G\right)\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 whose arc set is

$\begin{array}{c}A\left(D\right)\cup {\displaystyle \underset{i=1}{\overset{k}{\cup }}}{\displaystyle \underset{j=2}{\overset{{\alpha }_i}{\cup }}}\left\{\left(v_j^i,v_{j-2}^i\right)\right\}\cup {\displaystyle \underset{1\le i\le k,{\beta }_i>0}{\cup }}\left\{\left(x_1^i,v_{{\alpha }_i-1}^i\right)\right\}\cup {\displaystyle \underset{1\le i\le k,{\beta }_i=0}{\cup }}\left\{\left(v_1^{i+1},v_{{\alpha }_i-1}^i\right)\right\}\\ \cup {\displaystyle \underset{1\le i\le k,{\beta }_i>0}{\cup }}{\displaystyle \underset{j=1}{\overset{{\beta }_i}{\cup }}}\left\{\left(x_j^i,y_j^i\right),\left(x_{j+1}^i,y_j^i\right)\right\}-{\displaystyle \underset{i=1}{\overset{k}{\cup }}}\left\{\left(u^i,v_{{\alpha }_i-1}^i\right)\right\},\end{array}$

where $v_0^1=v_0$ and $v_0^i=x_{{\beta }_{i-1}}^{i-1}$ (if ${\beta }_{i-1}>0$ ) or $v_{{\alpha }_{i-1}}^{i-1}$ (if ${\beta }_{i-1}=0$ ) for any

$i\in \left\{\mathrm{2,3,}\cdots \mathrm{,}k\right\}$ , $x_{{\beta }_k+1}^k=v_1^1$ and $x_{{\beta }_i+1}^i=v_1^{i+1}$ for any $i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}k-1\right\}$ such that ${\beta }_i>0$ . All $y_j^i\left(1\le i\le k,1\le j\le {\beta }_i\right)$ are new added vertices.

We note that $D_1$ , $D_2$ and $D_3$ are acyclic. This is because every arc added here goes either from a big label vertex to a small label vertex or from a vertex in $V\left(G\right)$ to a new added vertex not in $V\left(G\right)\cup \left\{v_0\right\}$ . It is not difficult to check that

$C\left(D_1\right)=G\cup \left\{v_0,v_1\right\},$

$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.