Open Journal of Discrete Mathematics
Vol.07 No.01(2017), Article ID:73213,10 pages
10.4236/ojdm.2017.71002
Competition Numbers of a Kind of Pseudo-Halin Graphs
Zhijun Cao, Yonggang Cui, Guoyan Ye, Yongqiang Zhao*
School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China
Copyright © 2017 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: October 9, 2016; Accepted: December 27, 2016; Published: December 30, 2016
ABSTRACT
For any graph , together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number of a graph is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number for a graph 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 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 . In this paper, we compute the competition numbers of a kind of pseudo-Halin graphs.
Keywords:
Competition Graph, Competition Number, Halin Graph, Generalized Halin Graph, Pseudo-Halin Graph
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
Figure 1. and .
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
Figure 2. 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.
Cite this paper
Cao, Z.J., Cui, Y.G., Ye, G.Y. and Zhao, Y.Q. (2017) Com- petition Numbers of a Kind of Pseudo- Halin Graphs. Open Journal of Discrete Mathematics, 7, 3-12. http://dx.doi.org/10.4236/ojdm.2017.71002
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