Competition Numbers of a Kind of Pseudo-Halin Graphs

Zhijun  Cao; Yonggang  Cui; Guoyan  Ye; Yongqiang  Zhao

doi:10.4236/ojdm.2017.71002

Zhijun Cao, Yonggang Cui, Guoyan Ye, Yongqiang Zhao^*

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₀ yields a tree. It is a Halin graph if the vertices of f₀ all have degree 3 in G. 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

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.

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