1. Introduction and Preliminary
Let
be a graph in which
is the vertex set and
the edge set. We always use
and
to denote the vertex number and the edge number of
, respectively. The notion of competition graph was introduced by Cohen [1] in connection with a problem in ecology. Let
be a digraph in which
is the vertex set and
the set of directed arcs. The competition graph
of
is the undirected graph
with the same vertex set as
and with an edge
if and only if there exists some vertex
such that
. We say that a graph
is a competition graph if there exists a digraph
such that
.
*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
of a graph
is defined to be the smallest number
such that
together with
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
to denote the graph consisting only of
isolated vertices, and
the disjoint union of
and
. The induced subgraph
of
is a subgraph of
whose vertex set is
and whose edge set is the set of those edges of
that have both ends in
.
All graphs considered in this paper are simple and connected. For a vertex
in a graph G, let the open neighborhood of
be denoted by
. For any set
of vertices in
, we define the neighborhood of
in
to be the set of all vertices adjacent to vertices in
, this set is denoted by
. An in-neighbor of a vertex
in digraph
is a vertex
such that
; an out-neighbor of a vertex
is a vertex
such that
. We denote the sets of in-neighbors and out-neighbors of
in
by
and
, re- spectively.
A subset
of the vertex set of a graph
is called a clique of
if
is a complete graph. For a clique
of a graph
and an edge
of
, we say
is covered by
if both of the endpoints of
are contained in
. An edge clique cover of a graph
is a family of cliques such that each edge of
is covered by some clique in the family. The edge clique cover number
of a graph
is the minimum size of an edge clique cover of
. A vertex clique cover of a graph
is a family of cliques such that each vertex of
is contained in some clique in the family. The vertex clique cover number
of a graph
is the minimum size of a vertex clique cover of
.
A generalized Halin graph
is a plane graph consisting of a plane embedding of a tree
and a cycle
connecting the leaves (vertices of degree 1) of
such that
is the boundary of the exterior face. The tree
and the cycle
are called the characteristic tree and the adjoint cycle of
, respectively. For each
, if
for any vertex
, then we called
a simple leaf of
, otherwise, a compound leaf of
. Denote all simple leaves of
by
and all compound leaves of
by
, respectively. It is obvious that
, and
. Let
,
. A generalized Halin graph
is a Halin graph when each interior vertex of
has degree at least 3.
A 2-connected planar graph
with minimum degree at least 3 is a pseudo-Halin graph if deleting the edges on the boundary of a single face
yields a tree. It is a Halin graph if the vertices of
all have degree 3 in
. The face
is the exterior face; the others are interior faces. Vertices of
are exterior vertices; the others are interior vertices. Vertices of
with degree 3 in
are regular vertices; the others are irregular vertices. Let
and
denote the sets of regular and irregular vertices in
, respectively.
The main theme of this paper is to study the competition numbers of a kind of pseudo-Halin graphs with
, 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
be a digraph. Then
is acyclic if and only if there exists an ordering of vertices,
, such that one of the following two conditions holds:
1) For all
,
implies that
;
2) For all
,
implies that
.
By this lemma, if
is an acyclic digraph, we can find a vertex labelling
so that whenever
,
. We call
an acyclic labelling of
. Conversely, if
is a digraph with an acyclic labelling, then
is acyclic.
Lemma 2 (Kim and Roberts [4] ). For a tree
and a vertex
of
, there is an acyclic digraph
so that
is the competition graph of
for
not in
and so that
has only outgoing arcs in
.
Kim and Roberts [4] proved Lemma 2 by the following algorithm.
Let
,
, and
. Choose a vertex
of degree 1 from
. If
is adjacent to
in
, let
,
for some vertex
not in
, and
. Having defined
and
, choose a vertex
of degree 1 from
. If
is adjacent to
in
, then let
,
, and
. Repeat this last step until
has been defined. Let
. In the procedure, we may avoid selecting
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
of
such that
,
, and
and
have only outgoing arcs in
, where
.
Opsut [3] gave the following two lower bounds for the competition number of a graph.
Theorem 1 (Opsut [3] ). For any graph
,
.
Theorem 2 (Opsut [3] ). For any graph
,
.
Lemma 3. For any generalized Halin graph
,
Proof. Let
be a generalized Halin graph, where
and
are the characteristic tree and the adjoint cycle of
, respectively. Suppose that along cycle
by clockwise order we can partition
(if
) into
subsets
such that
and the vertices in each
are con- secutive on
, where
. Let
be the common neighbor of the vertices in
, where
. We assume that the vertices in
by clockwise order are
, where
and
. Denote all vertices on
between
and
by
, where
and
. We assume that the vertices in
(if
) by clockwise order are
, where
and
. Note that
, and if
then we always let
. If
, then let
and arbitrarily select a vertex in
as
.
By Lemma 1 and the algorithm in the proof of Lemma 2, we can construct an acyclic digraph
so that
is the competition graph of
for
not in
, and get an acyclic labelling
of
so that
Note that, if
, then let
, if
, then let
, where
, and we always have
and
. Label the
other vertices of
arbitrarily.
Case 1.
.
Let
be a digraph whose vertex set is
and whose arc set is
where
,
for each
, and
are new added vertices.
Case 2.
.
Let
be a digraph whose vertex set is
and whose arc set is
where
, and all
are new added vertices.
Case 3.
and
.
Let
be a digraph whose vertex set is
and whose arc set is
where
and
(if
) or
(if
) for any
,
and
for any
such that
. All
are new added vertices.
We note that
,
and
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
to a new added vertex not in
. It is not difficult to check that
And we know that
if
, and
if
and
. So the result follows.
Lemma 4. For any not
generalized Halin graph
,
Proof. Let
be a not
generalized Halin graph, where
and
are the characteristic tree and the adjoint cycle of
, respectively. Since
is a tree, then
. Note that
just includes all triangles in
and the edges in
, so
. It is easy to check that
. Furthermore, each pair of graphs
,
and
has not any common edges. So we have
or
3. Pseudo-Halin Graph
Now we consider a pseudo-Halin graph
with the exterior face
and
. Let
and
be the neighbors of
on the boundary of
. Without lose of generality, we may always assume that
is on the left of
and
on the right of
. Let
. Note that
is a generalized Halin graph since
is accepted. See Figure 1. Let
, where
and
are the characteristic tree and the adjoint cycle of
, respectively. Then it is easy to see that
is got from the boundary of
by deleting the edges
and
, and adding the edge
. So we have
. Let
be another neighbor of
on cycle
. The characteristic tree
of
is just the tree got from
by deleting the edges on the boundary of the face
. So
may also be called the characteristic tree of
. Let
be the neighbor of
in
and
the neighbor of
in
, respectively.
We construct a graph
from
by replacing the edge
by a path
, and joining
with
. It is not difficult to see that
is a Halin graph. Since every Halin graph contains a triangle, and
is not a vertex of any triangle in
, then
also contains a triangle. Therefore
. So we just need to consider the following cases.
Theorem 3. Let
be a pseudo-Halin graph with
, and
the adjoint cycle of graph
. If
, then
.
Proof. Suppose that G is a pseudo-Halin graph with
and
, where
is the adjoint cycle of graph
. Denote and labelling the vertices of
in a similar way as used in Lemma 3. By Lemma 3,
. Let
and by the similar way used in the proof of Lemma 3, there is a digraph
such that
and
but
where
and
are two isolated vertices not in
. Note that
. Let
and
See Figure 2. Note that
is acyclic since every arc added here goes from a big label vertex to a small label vertex. It is easy to see that
So we have
. On the other hand, since for each vertex
,
, and note that the maximal clique in
is a triangle, so we have
. By Theorem 2,
. Therefore
.
Lemma 5. Let
be a pseudo-Halin graph with
, and
the adjoint cycle of graph
. If
, then we have
.
Proof. Suppose that
is a pseudo-Halin graph with
and
, where
is the adjoint cycle of graph
. Denote and labelling the vertices of
in a similar way as used in Lemma 3. By Lemma 3,
, and there is a digraph
such that
, where
are
isolated vertices not in
. By the similar way used in the proof of Lemma 3, there exists a vertex
or
such that
. Let
and
where
is a new added vertex to
. Note that
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
. So we have
.
Lemma 6. Let
be a pseudo-Halin graph with
, and
the adjoint cycle of graph
.
1) If
, then
,
2) If
, then
3) If
, but
, then
where
.
Proof. 1)
.
Obviously,
and
are two maximal cliques of
. Since
is a maximal clique of
, then
.
2)
.
It is easy to see that
and
are two maximal cliques of
. Note that
is a maximal clique of
. If
, then
,
,
and
are all maximal cliques of graph
. So
; If
, then
and
are two maximal cliques of graph
, but
and
not. Hence
; Otherwise, say
and
. Then
,
and
are all maximal cliques of graph
, but
not. Therefore
.
3)
but
(or
but
).
Without lose of generality, we just need to consider the case
but
. By the proof of Case (1),
. If
, then
and
are all maximal cliques of graph
. If
, then
is a maximal clique of graph
, but
not. So the result follows.
For a pseudo-Halin graph
, suppose that
be the exterior face of
and
. Note that
can not be
, so by Lemmas 4 we have
, by Lemma 5 we have
. On the other hand, by Theorem 1 we have
. So by lemmas 6, we have the following result.
Theorem 4. Let
be a pseudo-Halin graph with
and
, where
is the adjoint cycle of graph
.
1) If
, then
,
2) If
, then
3) If
, and
, then
where
.
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
with the exterior face
and
, we show that if all leaves of the characteristic tree of
are compound leaves, then
, otherwise,
. Even we proved that
for some cases, but we can not provide the accurate value of the competition number of
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
, if we partition
into
types, then we may construct a undirected graph
of
as follows
1)
if and only if there exists some vertex
such that
and
are of same type, or
2)
if and only if there exists some vertex
such that
and
are of different types.
It is easy to see that
for a given digraph
, 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.