Research ArticleOpen AccessGoogle Scholar indexed
Competition Numbers of a Kind of Pseudo-Halin Graphs
School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China
School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China
School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China
School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China
- 1 School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China
- 2 School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China
- 3 School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China
- 4 School of Mathematics and Information Science, Shijiazhuang University, Shijiazhuang, China
Open Journal of Discrete Mathematics·Volume 07 (2016)·Pages 3–12·Published 6 December 2016·DOI10.4236/ojdm.2017.71002
Copy link · social · email
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.
KeywordsCompetition GraphCompetition NumberHalin GraphGeneralized Halin GraphPseudo-Halin Graph
- Cohen, J.E. (1968) Interval Graphs and Food Webs: A Finding and a Problem. Document 17696-PR, RAND Corporation, Santa Monica, CA.
- 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
- 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
- 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
- Sano, Y. (2009) The Competition Numbers of Regular Polyhedra. Congressus Numerantium, 198, 211-219.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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