Back
 OJDM  Vol.7 No.2 , April 2017
Competition Numbers of Several Kinds of Triangulations of a Sphere
Abstract: It is hard to compute the competition number for a graph in general and characterizing a graph by its competition number has been one of important research problems in the study of competition graphs. Sano pointed out that it would be interesting to compute the competition numbers of some triangulations of a sphere as he got the exact value of the competition numbers of regular polyhedra. In this paper, we study the competition numbers of several kinds of triangulations of a sphere, and get the exact values of the competition numbers of a 24-hedron obtained from a hexahedron by adding a vertex in each face of the hexahedron and joining the vertex added in a face with the four vertices of the face, a class of dodecahedra constructed from a hexahedron by adding a diagonal in each face of the hexahedron, and a triangulation of a sphere with 3n (n≥2) vertices.
Cite this paper: Zhao, Y. , Fang, Z. , Cui, Y. , Ye, G. and Cao, Z. (2017) Competition Numbers of Several Kinds of Triangulations of a Sphere. Open Journal of Discrete Mathematics, 7, 54-64. doi: 10.4236/ojdm.2017.72006.
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 (International Proceding Conference, Western Michigan University, Kalamazoo, Michigan, 1976), 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.
https://doi.org/10.7151/dmgt.1506

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

[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 -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]   Cho, H.H. and Kim, S.R. (2005) The Competition Number of a Graph Having Exactly One Hole. Discrete Mathematics, 303, 32-41.
https://doi.org/10.1016/j.disc.2004.12.016

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

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

[18]   Kim, S.R. (2005) Graphs with One Hole and Competition Number One. Journal of the Korean Mathematical Society, 42, 1251-1264.
https://doi.org/10.4134/JKMS.2005.42.6.1251

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

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

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

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

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

[24]   Sano, Y. (2013) A Generalization of Opsut’s Lower Bounds for the Competition Number of a Graph. Graphs and Combinatorics, 29, 1543-1547.
https://doi.org/10.1007/s00373-012-1188-5

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

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

[27]   Shang, Y. (2016) Groupies in Multitype Random Graphs. SpringerPlus, 5, 989.
https://doi.org/10.1186/s40064-016-2705-4

 
 
Top