Competition Numbers of a Kind of Pseudo-Halin Graphs

Affiliation(s)

School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China.

School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China.

ABSTRACT

For any graph*G*, *G *together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number *k*(*G)* of a graph *G* is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number *k*(*G)* for a graph *G* and chara-cterizing a graph by its competition number has been one of important research problems in the study of competition graphs. 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*. In this paper, we compute the competition numbers of a kind of pseudo-Halin graphs.

For any graph

KEYWORDS

Competition Graph, Competition Number, Halin Graph, Generalized Halin Graph, Pseudo-Halin Graph

Competition Graph, Competition Number, Halin Graph, Generalized Halin Graph, Pseudo-Halin Graph

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{\hspace{0.17em}}\text{\hspace{0.05em}}\text{is}\text{\hspace{0.17em}}\text{adjacent}\text{\hspace{0.17em}}\text{to}\text{\hspace{0.05em}}\text{\hspace{0.17em}}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{\hspace{0.17em}}\text{\hspace{0.05em}}\text{and}\text{\hspace{0.05em}}$

$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}^{\u2033}$ 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}^{\u2033}$ is a Halin graph. Since every Halin graph contains a triangle, and ${x}^{\prime}$ is not a vertex of any triangle in ${G}^{\u2033}$ , 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{,}$

Figure 1. $G$ and ${G}^{\prime}$ .

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 \mathrm{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\},$

Figure 2. $G$ and $D$ $\left({V}_{1}=\varnothing \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{\hspace{0.05em}}\text{otherwise,}\text{\hspace{0.05em}}\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.

Cite this paper

Cao, Z. , Cui, Y. , Ye, G. and Zhao, Y. (2017) Competition Numbers of a Kind of Pseudo-Halin Graphs.*Open Journal of Discrete Mathematics*, **7**, 3-12. doi: 10.4236/ojdm.2017.71002.

Cao, Z. , Cui, Y. , Ye, G. and Zhao, Y. (2017) Competition Numbers of a Kind of Pseudo-Halin Graphs.

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, Lecture Notes in Mathematics, 642, 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.

[6] Kim, S.-R., Park, B. and Sano, Y. (2010) The Competition Numbers of Johnson Graphs. Discussiones Mathematicae Graph Theory, 30, 449-459.

https://doi.org/10.7151/dmgt.1506

[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 r-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] 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

[16] 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

[17] 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

[18] 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

[19] 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

[20] 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.

[21] 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

[22] Harary, F., Norman, R.Z. and Cartwright, D. (1965) Structure Models: An Introduction to the Theory of Directed Graphs. Wiley, New York.

[23] 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

[24] Shang, Y. (2016) Groupies in Multitype Random Graphs. SpringerPlus, 5, 989.

https://doi.org/10.1186/s40064-016-2705-4

[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, Lecture Notes in Mathematics, 642, 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.

[6] Kim, S.-R., Park, B. and Sano, Y. (2010) The Competition Numbers of Johnson Graphs. Discussiones Mathematicae Graph Theory, 30, 449-459.

https://doi.org/10.7151/dmgt.1506

[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 r-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] 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

[16] 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

[17] 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

[18] 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

[19] 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

[20] 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.

[21] 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

[22] Harary, F., Norman, R.Z. and Cartwright, D. (1965) Structure Models: An Introduction to the Theory of Directed Graphs. Wiley, New York.

[23] 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

[24] Shang, Y. (2016) Groupies in Multitype Random Graphs. SpringerPlus, 5, 989.

https://doi.org/10.1186/s40064-016-2705-4